配点: 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 点): N \leq 10000, \ B \leq 30
- (3 点): B \leq 30
- (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 约束。