問題一覧 > 通常問題

No.1417 Multiple of 100 and Positive Integer (2)

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 162
作問者 : H20 / テスター : 👑 hamamu Kanten4205
お気に入りにしたユーザー ProblemId : 5959 / 自分の提出
問題文最終更新日: 2021-02-25 00:02:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 285 (順位表) の他の問題:

Problem Statement

For a positive integer, define its digit product as the value obtained by multiplying all of its digits together.
For example, the digit product of $3142$ is $24$ ($3×1×4×2=24$), and the digit product of $10$ is $0$ ($1×0=0$).
Among the integers between $1$ and $N$, inclusive, find the number of integers whose digit product is a multiple of $100$ and a positive integer.
Since this value can be very large, output the remainder when it is divided by $10^9+7$.

Input

$N$

  • $ 1 \le N \le 10^{10000}$
  • All inputs are integers.

Output

Output the number of integers satisfying the condition, modulo $10^9+7$, followed by a newline.

Sample

Sample 1
Input
1000
Output
6

$455$, $545$, $554$, $558$, $585$, and $855$ satisfy the condition.

Sample 2
Input
123456
Output
4295

Sample 3
Input
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Output
207718052

This is the input for $N=10^{100}$. $N$ can take larger values than this.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。