B - 連番チケットの当選 解説 /

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

配点 : 333 点

問題文

高橋君は宝くじ売り場で働いています。この宝くじでは、1 から N までの番号がそれぞれ印刷されたチケットが 1 枚ずつ、合計 N 枚販売されています。当選条件はチケット番号の桁和によって決まります。ここで、正の整数の桁和とは、その 10 進表記における各桁の数字の合計のことです。例えば、123 の桁和は 1 + 2 + 3 = 6 です。

具体的には、チケット番号の桁和を K で割った余りが R に等しいとき、そのチケットは「当選チケット」となります。

高橋君は、連続する 3 つの番号 x-1, x, x+1 のチケットがすべて当選チケットになるようなケースに興味を持ちました。

正の整数 N、正の整数 K、非負整数 R が与えられます。整数 n の桁和を \mathrm{digitsum}(n) と書くとき、2 \leq x \leq N - 1 を満たす整数 x であって、

(\mathrm{digitsum}(x-1)) \bmod K = R, \quad (\mathrm{digitsum}(x)) \bmod K = R, \quad (\mathrm{digitsum}(x+1)) \bmod K = R

の 3 条件をすべて満たす整数 x の個数を 10^9 + 7 で割った余りを求めてください。

制約

  • N は 3 以上の整数
  • N は 10 進表記の文字列として与えられ、先頭に不要な 0 を含まない
  • N の 10 進表記の長さは 5 \times 10^6 以下
  • 1 \leq K \leq 100
  • 0 \leq R \leq K - 1

入力

N K R

入力は 1 行からなり、チケット番号の上限 N、除数 K、余り R がスペース区切りで与えられる。N は非常に大きい場合があるため、10 進表記の文字列として与えられる。K と R は整数として与えられる。

出力

条件を満たす整数 x の個数を 10^9 + 7 で割った余りを 1 行で出力せよ。

入力例 1

25 3 1

出力例 1

0

入力例 2

50 7 0

出力例 2

0

入力例 3

123456789 9 6

出力例 3

0

入力例 4

100000000000000000000000000000000000000000000000000 97 42

出力例 4

0

入力例 5

3 1 0

出力例 5

1

Score : 333 pts

Problem Statement

Takahashi works at a lottery ticket booth. In this lottery, a total of N tickets are sold, each printed with a unique number from 1 to N. The winning condition is determined by the digit sum of the ticket number. Here, the digit sum of a positive integer is the sum of its digits in its decimal representation. For example, the digit sum of 123 is 1 + 2 + 3 = 6.

Specifically, a ticket is a "winning ticket" if the digit sum of its ticket number modulo K is equal to R.

Takahashi became interested in cases where three consecutive ticket numbers x-1, x, x+1 are all winning tickets.

You are given a positive integer N, a positive integer K, and a non-negative integer R. Let \mathrm{digitsum}(n) denote the digit sum of an integer n. Find the number of integers x satisfying 2 \leq x \leq N - 1 such that all of the following three conditions are met, modulo 10^9 + 7:

(\mathrm{digitsum}(x-1)) \bmod K = R, \quad (\mathrm{digitsum}(x)) \bmod K = R, \quad (\mathrm{digitsum}(x+1)) \bmod K = R

Constraints

  • N is an integer of at least 3
  • N is given as a string in decimal representation, without leading zeros
  • The length of the decimal representation of N is at most 5 \times 10^6
  • 1 \leq K \leq 100
  • 0 \leq R \leq K - 1

Input

N K R

The input consists of a single line containing the upper bound of the ticket numbers N, the divisor K, and the remainder R, separated by spaces. Since N can be extremely large, it is given as a string in decimal representation. K and R are given as integers.

Output

Print the number of integers x satisfying the conditions, modulo 10^9 + 7, in a single line.

Sample Input 1

25 3 1

Sample Output 1

0

Sample Input 2

50 7 0

Sample Output 2

0

Sample Input 3

123456789 9 6

Sample Output 3

0

Sample Input 4

100000000000000000000000000000000000000000000000000 97 42

Sample Output 4

0

Sample Input 5

3 1 0

Sample Output 5

1