D - 88888888 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 350 点

問題文

正整数 N に対して、N を N 個つなげた整数を V_N とします。
より厳密には、N を文字列とみなしたものを N 個連結し、 それを再度整数とみなしたものを V_N とします。
例えば、V_3=333, V_{10}=10101010101010101010 です。

V_N を 998244353 で割った余りを求めてください。

制約

  • 1\leq N\leq 10^{18}
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

V_N を 998244353 で割った余りを出力せよ。

入力例 1

5

出力例 1

55555

V_5=55555 を 998244353 で割った余りは 55555 です。

入力例 2

9

出力例 2

1755646

V_9=999999999 を 998244353 で割った余りは 1755646 です。

入力例 3

10000000000

出力例 3

468086693

入力が 32 bit 整数型に収まらない可能性があることに注意してください。

Score : 350 points

Problem Statement

For a positive integer N, let V_N be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get V_N.
For example, V_3=333 and V_{10}=10101010101010101010.

Find the remainder when V_N is divided by 998244353.

Constraints

  • 1 \leq N \leq 10^{18}
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print the remainder when V_N is divided by 998244353.

Sample Input 1

5

Sample Output 1

55555

The remainder when V_5=55555 is divided by 998244353 is 55555.

Sample Input 2

9

Sample Output 2

1755646

The remainder when V_9=999999999 is divided by 998244353 is 1755646.

Sample Input 3

10000000000

Sample Output 3

468086693

Note that the input may not fit into a 32-bit integer type.