E - 数 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

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

Constraints

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

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

3
100

Sample Output 1

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

Sample Input 2

7
123456789012345678901234567890

Sample Output 2

468357804