#111 jkrt's AND

Statement

Statement language

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,

3054 \operatorname{AND} 1043 = 2.

List all positive integers $x$ satisfying

x \operatorname{AND} (x-1)=0

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

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

Input

The input is given in the following format.

$N$

Output

Print $A_N$ modulo $998244353$ .

Constraints

$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.

Subtasks

#	Score	Constraints
1	100	Full constraints.

Samples

Sample 1

Input

1

Output

1

Since $1 \operatorname{AND} 0 = 0$ , we have $A_1=1$ .

Sample 2

Input

10

Output

10