Two Sorts
题意翻译
## 题目描述
有一个数列 $ \{a_1,a_2,\dots,a_n\}$是一个1~n的排列，且所有的数都按照**字典序**排序，现在给出整数 $n(1\le n\le 10^{12})$， 求 $(\sum_{i=1}^{n}((i-a_i)\mod 998244353))\mod 10^9+7$ ，注意这里的 $x\mod y$的结果为正数
## 输入格式
一行一个正整数 $n$
## 输出格式
一行一个非负整数，代表你的答案
题目描述
Integers from $ 1 $ to $ n $ (inclusive) were sorted lexicographically (considering integers as strings). As a result, array $ a_1, a_2, \dots, a_n $ was obtained.
Calculate value of $ (\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7 $ .
$ x \mod y $ here means the remainder after division $ x $ by $ y $ . This remainder is always non-negative and doesn't exceed $ y - 1 $ . For example, $ 5 \mod 3 = 2 $ , $ (-1) \mod 6 = 5 $ .
输入输出格式
输入格式
The first line contains the single integer $ n $ ( $ 1 \leq n \leq 10^{12} $ ).
输出格式
Print one integer — the required sum.
输入输出样例
输入样例 #1
3
输出样例 #1
0
输入样例 #2
12
输出样例 #2
994733045
输入样例 #3
21
输出样例 #3
978932159
输入样例 #4
1000000000000
输出样例 #4
289817887
说明
A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds:
- $ a $ is a prefix of $ b $ , but $ a \ne b $ ;
- in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .
For example, $ 42 $ is lexicographically smaller than $ 6 $ , because they differ in the first digit, and $ 4 < 6 $ ; $ 42 < 420 $ , because $ 42 $ is a prefix of $ 420 $ .
Let's denote $ 998244353 $ as $ M $ .
In the first example, array $ a $ is equal to $ [1, 2, 3] $ .
- $ (1 - 1) \mod M = 0 \mod M = 0 $
- $ (2 - 2) \mod M = 0 \mod M = 0 $
- $ (3 - 3) \mod M = 0 \mod M = 0 $
As a result, $ (0 + 0 + 0) \mod 10^9 + 7 = 0 $
In the second example, array $ a $ is equal to $ [1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9] $ .
- $ (1 - 1) \mod M = 0 \mod M = 0 $
- $ (2 - 10) \mod M = (-8) \mod M = 998244345 $
- $ (3 - 11) \mod M = (-8) \mod M = 998244345 $
- $ (4 - 12) \mod M = (-8) \mod M = 998244345 $
- $ (5 - 2) \mod M = 3 \mod M = 3 $
- $ (6 - 3) \mod M = 3 \mod M = 3 $
- $ (7 - 4) \mod M = 3 \mod M = 3 $
- $ (8 - 5) \mod M = 3 \mod M = 3 $
- $ (9 - 6) \mod M = 3 \mod M = 3 $
- $ (10 - 7) \mod M = 3 \mod M = 3 $
- $ (11 - 8) \mod M = 3 \mod M = 3 $
- $ (12 - 9) \mod M = 3 \mod M = 3 $
As a result, $ (0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7 $ $ = $ $ 2994733059 \mod 10^9 + 7 $ $ = $ $ 994733045 $