该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

数

题面翻译

求小于等于 $N$ 的正整数中有多少个在十进制表示下数码和是 $D$ 的倍数。答案模 $10 ^ 9 + 7$ 后输出。

题目描述

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

输入格式

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

$D$

$N$

输出格式

答えを一行に出力せよ。

样例 #1

样例输入 #1

3
100

样例输出 #1

33

样例 #2

样例输入 #2

7
123456789012345678901234567890

样例输出 #2

468357804

提示

Constraints

• $1 \le N \le 10^{10000}$
• $1 \le D \le 100$

Sample Explanation 1

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