jkrt의 AND

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

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

이다.

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

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

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

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

$N$

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

• $N$은 십진 표기로 주어지는 양의 정수이다.
• $1 \le N < 10^{200000}$.
• $N$의 십진 표기에는 leading zero가 없다.