E - Digit Circus 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

1 以上 N 以下の整数 x であって、以下の 3 つの条件のうちちょうど \mathbf{1} つだけを満たすものの個数を 998244353 で割ったあまりを求めてください。

  • x は 3 の倍数である
  • x の十進表記には 3 が含まれる
  • x の十進表記にはちょうど 3 種類の数字が使われる

なお、整数の十進表記は先頭に不要な 0 をつけないものとします。

制約

  • N は整数
  • 1 \leq N < 10^{500}

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

45

出力例 1

19

1 以上 45 以下の整数であって、問題文中の条件のうちちょうど 1 つを満たすものは以下の 19 個です。

  • 1 番目の条件だけを満たす整数は 6, 9, 12, 15, 18, 21, 24, 27, 42, 45 の 10 個
  • 2 番目の条件だけを満たす整数は 13, 23, 31, 32, 34, 35, 37, 38, 43 の 9 個
  • 3 番目の条件だけを満たす整数は存在しない

入力例 2

1013

出力例 2

424

該当する整数の例として以下が挙げられます。

  • 1 番目の条件だけを満たす整数は 555 や 1011 など
  • 2 番目の条件だけを満たす整数は 343 や 553 など
  • 3 番目の条件だけを満たす整数は 1012 や 704 など

入力例 3

2

出力例 3

0

該当する整数は 0 個です。

入力例 4

314159265358979323846264338327950

出力例 4

658111391

Score : 450 points

Problem Statement

Find, modulo 998244353, the number of integers x with 1 \leq x \leq N that satisfy exactly one of the following three conditions.

  • x is a multiple of 3.
  • The decimal representation of x contains 3.
  • Exactly three different digits are used in the decimal representation of x.

Here, the decimal representation of an integer should not have unnecessary leading 0s.

Constraints

  • N is an integer.
  • 1 \leq N < 10^{500}

Input

The input is given from Standard Input in the following format:

N

Output

Output the answer.

Sample Input 1

45

Sample Output 1

19

Among the integers from 1 to 45, there are 19 integers satisfying exactly one of the conditions in the problem statement, as follows.

  • There are 10 integers satisfying only the first condition: 6, 9, 12, 15, 18, 21, 24, 27, 42, 45.
  • There are 9 integers satisfying only the second condition: 13, 23, 31, 32, 34, 35, 37, 38, 43.
  • There are no integers satisfying only the third condition.

Sample Input 2

1013

Sample Output 2

424

Below are examples of applicable integers.

  • Integers satisfying only the first condition include 555 and 1011.
  • Integers satisfying only the second condition include 343 and 553.
  • Integers satisfying only the third condition include 1012 and 704.

Sample Input 3

2

Sample Output 3

0

There are no applicable integers.

Sample Input 4

314159265358979323846264338327950

Sample Output 4

658111391