7291: AtCoder Educational DP Contest —— S - Digit Sum
[Creator : ]
Description
Find the number of integers between 1 and K (inclusive) satisfying the following condition, modulo $10^9 + 7$:
- The sum of the digits in base ten is a multiple of D.
Input
Input is given from Standard Input in the following format:
$K$
$D$
$K$
$D$
Output
Print the number of integers satisfying the condition, modulo $10^9 + 7$.
Constraints
All values in input are integers.
$1 \leq K < 10^{10000}$
$1 \leq D \leq 100$
$1 \leq K < 10^{10000}$
$1 \leq D \leq 100$
Sample 1 Input
30
4
Sample 1 Output
6
Those six integers are: 4, 8, 13, 17, 22 and 26.
Sample 2 Input
1000000009
1
Sample 2 Output
2
Sample 3 Input
98765432109876543210
58
Sample 3 Output
635270834