#111 jkrt's AND

Loading problem...

Preparing the statement, recent submissions, and submit form.

#111 jkrt's AND | DOJ

Authors: jkrt

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

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

Output

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

Sample 2

Input

Output

The sequence starts with $1,2,\ldots,9,10,\ldots$ . Therefore, $A_{10}=10$ .

Sample 3

Input

Output

100

$A_{10},A_{11},\ldots,A_{17}$ are $10,20,\ldots,80$ , and the next value is $100$ .

Editorial

View editorial