Problem F
Hunter x Communication
Having passed the Hunter Exam, Gon is now officially a Hunter! Gon is now saying goodbye to his best friend, Killua, as Gon wants to visit his home in ‘While Island’.
Gon and Killua plan to use the online chat application, Olaz, to keep in touch. However, they are not confident with Olaz’s security: some imposters may be able to login to Gon’s account and send messages to Killua! To prevent this, they have decided to use the following method:
-
Before starting a conversation, Gon must send Killua a number $X$ with exactly $n$ digits.
-
Killua must reply with an integer $Y$ with exactly $n$ digits, where $X$ and $Y$ form a best friend pair.
-
Each time they start a conversation, they must use a different best friend pair. This would avoid imposters from simply reusing the previous best friend pairs.
To define a best friend pair, first we define a friendly operation on a number $X$ as follow:
-
Select two adjacent digits of $X$.
-
Either add $1$ to both digits, or subtract $1$ from both digits.
-
It is forbidden to add $1$ to digit $9$, or subtract $1$ from digit $0$.
-
It is also forbidden to subtract $1$ from the first digit of $X$, if the first digit of $X$ is $1$.
Note that the last two conditions guarantee that the new number is valid and does not have leading zero. The new and old numbers will also have the same length.
Two numbers $X$ and $Y$ without leading zeros are called best friends, if we can obtain $Y$ from $X$, by applying a finite number of friendly operations. Note that a number $X$ is best friend with itself.
For example, $666$ and $875$ are best friends because we can apply the operations as follow:
-
$666 \rightarrow 776$
-
$776 \rightarrow 886$
-
$886 \rightarrow 875$
Now Gon is wondering how many conversation can they have, before running out of best friend pairs.
Input
The input contains exactly one integer $n$ $(1 \le n \le 10^5)$.
Output
The output contains exactly one integer — the number of pairs of best friend numbers with exactly $n$ digits, modulo $998\, 244\, 353$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
10 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 |
570 |
