E - 数 Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

NN 以下の正整数であって、十進法表記したときの各桁の数の和が DD の倍数であるものの個数を mod 1,000,000,007 で求めよ。

Constraints

  • 1≤N≤10100001 ≤ N ≤ 10^{10000}
  • 1≤D≤1001 ≤ D ≤ 100

Input Format

入力は以下の形式で標準入力から与えられる。
DD
NN

Output Format

答えを一行に出力せよ。

Sample Input 1

3
100

Sample Output 1

33
1 以上 100 以下の 3 の倍数 33 個が条件を満たす。

Sample Input 2

7
123456789012345678901234567890

Sample Output 2

468357804

2025-04-04 (Fri)
22:27:07 +00:00