問題一覧 > 通常問題

No.315 Something of the World 3.5

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 52
作問者 : koyumeishi
お気に入りにしたユーザー ProblemId : 766 / 自分の提出
問題文最終更新日: 2026-06-25 02:58:34
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
Advent Calendar Contest 2015 (順位表) の他の問題:

Note

The time limit seems to be tight for some languages. Solving this in a fast language such as C++/Java/C# is recommended.

For reference

  • C++ passes in 442 ms without any particular effort.
  • The writer, an amateur at Java, tried hard in Java and passed in 1118 ms.
  • The writer, an amateur at C#, tried hard in C# and got TLE on 1–2 cases, but after copy-pasting camypaper's input/output methods it passed in 1747 ms.
  • The writer, an amateur at python, tried hard with pypy but it did not work (TLE). → With a bit more ingenuity it passed in about 1.2 sec. Several people have passed with python3.

Problem Statement

A comedian who imitates a certain comedian has appeared.
He becomes "aho" (silly) for "multiples of 3 or numbers containing the digit 3", and shows "hajirai" (shyness) for "multiples of $P$ ($P$ is one of 8, 80, 800)".
Among the integers between $A$ and $B$ inclusive, find the number of those for which he becomes "aho" and does not show "hajirai", modulo $10^9+7$.

Input

A B P

All inputs are given as integers.
$1 \leq A \leq B \leq 10^{200000} = 10^{2 \times 10^5}$
$P$ is one of 8, 80, 800

Output

Output the number of integers between $A$ and $B$ inclusive for which he becomes "aho" and does not show "hajirai", modulo $10^9+7$.

Sample

Sample 1
Input
1 100 8
Output
40

Sample 2
Input
114 514 80
Output
235

Sample 3
Input
1234 567890 800
Output
384205

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