Given a non-negative integer $x$, consider all integers in the interval $[0, 10^x - 1]$. Question: When these integers are written in decimal notation, how many times does the digit '1' appear in total? The answer should be taken modulo $998244353$.
(Hint: When you have no ideas, you might find some patterns or insights by generating a table for small ranges of data.)
Input
A single integer $x$ ($0 \le x \le 1000000$).
Output
Output a single integer representing the answer modulo $998244353$.
Examples
Input 1
2
Output 1
20
Input 2
0
Output 2
0
Note
When $x = 2$, the interval is $[0, 99]$. To write out these one hundred numbers, we need to write the digit '1' a total of 20 times, so the answer is 20.
When $x = 0$, the interval contains only the integer 0, and the answer is 0.