#111 jkrt's AND

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: jkrt

Statement

jkrt은 비트 연산을 몰라서, 두 음이 아닌 정수 $a,b$ 에 대해 $a \operatorname{AND} b$ 를 $a$ 와 $b$ 의 십진 표기의 LCS 길이로 정의하였다.

여기서 LCS란 최장 공통 부분수열을 뜻한다. 예를 들어 $3054$ 와 $1043$ 의 십진 표기에서 $04$ 는 공통 부분수열이고, 이보다 긴 공통 부분수열은 없으므로

3054 \operatorname{AND} 1043 = 2

이다.

모든 양의 정수 $x$ 중에서

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

을 만족하는 수들을 작은 순서대로 나열하자. 이때 $k$ 번째 수를 $A_k$ 라고 한다.

양의 정수 $N$ 이 주어진다. $A_N$ 을 $998244353$ 으로 나눈 나머지를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$

$A_N$ 을 $998244353$ 으로 나눈 나머지를 출력한다.

#	Score	Constraints
1	100	전체 제약을 만족하는 테스트입니다.

Sample 1

Input

Output

$1 \operatorname{AND} 0 = 0$ 이므로 $A_1=1$ 이다.

Sample 2

Input

Output

조건을 만족하는 수들은 $1,2,\ldots,9,10,\ldots$ 순서로 시작한다. 따라서 $A_{10}=10$ 이다.

Sample 3

Input

Output

100

$A_{10},A_{11},\ldots,A_{17}$ 은 각각 $10,20,\ldots,80$ 이고, 그 다음 수는 $100$ 이다.