/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N が与えられます。
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) に対し f(A) を次の手順で得られる整数とします。
- S を空文字列とする。
- i=1,2,\ldots,N の順番で以下の操作を行う。
- A_i を先頭に余分な 0 を付けない十進数の文字列としてみたものを T とする。
- S の末尾に T を連結する。
- S を十進数の整数としてみた値を f(A) とする。
例えば A=(1,20,34) に対し f(A)=12034 です。
(1,2,\ldots,N) の順列 P は全部で N! 通りありますが、それら全てに対する f(P) の総和を 998244353 で割ったあまりを求めてください。
制約
- 1\le N\le 2\times 10^5
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
1332
長さ 3 の順列は P=(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) の 6 通りありますが、それらに対する f(P) の値はそれぞれ f(P)=123,132,213,231,312,321 です。よって、 123+132+213+231+312+321=1332 を出力してください。
入力例 2
390
出力例 2
727611652
998244353 で割ったあまりを出力してください。
入力例 3
79223
出力例 3
184895744
Score : 600 points
Problem Statement
You are given a positive integer N.
For an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Let f(A) be the integer obtained as follows:
- Let S be an empty string.
- For i=1,2,\ldots,N in this order:
- Let T be the decimal representation of A_i without leading zeros.
- Append T to the end of S.
- Interpret S as a decimal integer, and let that be f(A).
For example, if A=(1,20,34), then f(A)=12034.
There are N! permutations P of (1,2,\ldots,N). Find the sum, modulo 998244353, of f(P) over all such permutations P.
Constraints
- 1 \le N \le 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Print the sum, modulo 998244353, of f(P) over all permutations P of (1,2,\ldots,N).
Sample Input 1
3
Sample Output 1
1332
The six permutations of (1,2,3) are (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Their f(P) values are 123,132,213,231,312,321. Therefore, print 123+132+213+231+312+321 = 1332.
Sample Input 2
390
Sample Output 2
727611652
Print the sum modulo 998244353.
Sample Input 3
79223
Sample Output 3
184895744