Problem Description

Consider a string of length $N$ consisting of $11$ types of characters: 1, 2, 3, 4, 5, 6, 7, 8, 9, +, and *.

There are a total of $11^N$ such strings, but you need to find the sum of the calculation results of all valid expressions among them, modulo $998244353$.

A string $S$ is considered a valid expression if:

• The first and last characters of $S$ are not + or *.
• When taking any two consecutive characters from $S$, at least one of them is not + or *.

All integers in the expression are in decimal notation, and the calculation follows standard arithmetic rules. For example, the calculation result of the string 22+3*4 is $34$.

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

1

Sample Output #1

45

Sample Input #2

3

Sample Output #2

407430

Sample Input #3

1000000000000000000

Sample Output #3

493565653

Notes/Hints

Constraints

• $1 \leq N \leq 10^{18}$
• All inputs are integers.

Sample Explanation 1

The possible strings are 1, 2, 3, 4, 5, 6, 7, 8, 9, and their respective calculation results are $1, 2, 3, 4, 5, 6, 7, 8, 9$. Therefore, the value to be found is the sum of these, which is $45$.

Sample Explanation 2

Examples of valid expressions include 239, 2+5, 5*8, etc.

见题面 Input 部分

见题面 Output 部分