問題一覧 > 通常問題

No.1417 100の倍数かつ正整数(2)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 159
作問者 : H20 / テスター : hamamu Kanten4205
6 ProblemId : 5959 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-25 00:02:53

問題文

ある正の整数について各桁の数字を掛け合わせた値を桁掛と定義します。
例えば、3142 の桁掛は24 (3×1×4×2=24) 、10 の桁掛は0 (1×0=0)です。
1以上N以下の整数のうち、その整数の桁掛が100の倍数かつ正整数である個数を求めてください。
ただし、この値は非常に大きくなることがあるので、109+7で割った余りを出力してください。

入力

N

  • 1≤N≤1010000
  • 入力は全て整数

出力

条件を満たす個数を109+7で割った余りを出力し、最後に改行してください。

サンプル

サンプル1
入力
1000
出力
6

455、545、554、558、585、855 が該当します。

サンプル2
入力
123456
出力
4295

サンプル3
入力
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
出力
207718052

N=10100の入力です。Nはこれより大きな値をとることがあります。

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