Math String

Time limit2sMemory limit1024 MB

Summary

Sum the values of all length-N strings over digits 1-9 and the operators + and * that form valid expressions, modulo 998244353, with N up to 1e18.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics, Matrix
Solved: No attempts yet

Problem

Consider a string $S$ of length $N$ made of 11 characters: '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '*'.

A string $S$ is called a math string if:

The first and last characters of $S$ are neither '+' nor '*'.
For any two consecutive characters of $S$ , at least one of them is neither '+' nor '*'.

Every math string can be read as an arithmetic expression built from integers in decimal notation and the ordinary arithmetic operations, where multiplication takes precedence over addition. The value of each such expression can be computed: for example, the math string "35+2*6" has value $47$ . Find the sum of the values of all math strings of length $N$ , modulo $998\,244\,353$ .

Input

The input consists of one integer $N$ . ( $1 \le N \le 10^{18}$ )

Output

Print one integer, the answer to the problem.

Notes

In sample 1 there are only 9 distinct one-digit math strings: the digits '1' through '9'. The sum of those digits, read as arithmetic expressions, is $45$ .

Examples3

Example 1
Input
```
1
```
Expected output
```
45
```
Example 2
Input
```
3
```
Expected output
```
407430
```
Example 3
Input
```
1000000000000000000
```
Expected output
```
493565653
```