← 返回题目列表

AtCoder · tdpc_number

E. 数

中文机器翻译题面 查看原题

问题陈述

N 以下的正整数中,当用十进制表示时,各位数字之和为 D 的倍数的个数,请对 1,000,000,007 取模求出。

约束

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

输入格式

输入将以以下形式从标准输入给出。
D
N

输出格式

请将答案输出为一行。

示例输入 1

3
100

示例输出 1

33
1 到 100 之间的 3 的倍数有 33 个符合条件。

示例输入 2

7
123456789012345678901234567890

示例输出 2

468357804