005 - Restricted Digits(★7)
Editorial
/
Time Limit: 5 sec / Memory Limit: 1024 MB
配点: 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 のみの制約を満たします。