/ 
Time Limit: 2 sec / Memory Limit: 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