問題文

数字 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 点)： 追加の制約はない。

入力例 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 のみの制約を満たします。