← 返回题目列表

AtCoder · typical90_e

005. 限制数字(★7)

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

配点: 7 点

問題文

数字 c_1,c_2, \dots ,c_K 仅使用可构造 N 位正整数中 B 的倍数有多少。 10^9 + 7 求除以后的余数。

制約

  • 1 \leq K \leq 9
  • 1 \leq c_1 \lt c_2 \lt \cdots \lt c_K \leq 9
  • 1 \leq N \leq 10^{18}
  • 2 \leq B \leq 1000
  • 所有输入均为整数

小课题·得点

这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。

  1. (1 点): N \leq 10000, \ B \leq 30
  2. (3 点): B \leq 30
  3. (3 分):没有额外约束。

入力

输入是按以下格式从标准输入给出的。

N B K
c_1 c_2 \cdots c_K

出力

答案 请打印除以 10^9 + 7 后的余数。


入力例 1

3 7 3
1 4 9

出力例 1

3

1, 4, 9 可由 3 数字 7 的倍数有 119, 441, 994 可以得到第 3 件。


入力例 2

5 2 3
1 4 9

出力例 2

81

入力例 3

10000 27 7
1 3 4 6 7 8 9

出力例 3

989112238

入力例 4

1000000000000000000 29 6
1 2 4 5 7 9

出力例 4

853993813

*此输入示例是一个小作业 仅满足 2, 3 约束。


入力例 5

1000000000000000000 957 7
1 2 3 5 6 7 9

出力例 5

205384995

*此输入示例是一个小作业 仅满足 3 约束。