jkrt's AND

jkrt does not know bit operations, so for two nonnegative integers $a,b$, jkrt defines $a \operatorname{AND} b$ as the length of the LCS of the decimal representations of $a$ and $b$.

Here, LCS means the longest common subsequence. For example, $04$ is a common subsequence of the decimal representations of $3054$ and $1043$, and there is no longer common subsequence. Therefore,

List all positive integers $x$ satisfying

in increasing order. Let $A_k$ be the $k$-th such number.

Given a positive integer $N$, compute $A_N$ modulo $998244353$.

The input is given in the following format.

$N$

Print $A_N$ modulo $998244353$.

• $N$ is given in decimal notation and is a positive integer.
• $1 \le N < 10^{200000}$.
• The decimal representation of $N$ has no leading zero.