rachel is decorating her Christmas 🎄! To make her decorations, she starts with a numeric string ~S~. rachel then makes subsequences ~X_i~ of the string ~S~ by deleting a non-negative number of characters from ~S~, but not changing their order. Note that ~2~ subsequences are distinct if the set of their deleted indices are different, and a subsequence must have a positive length. She then goes to the store to buy all the string decorations for each subsequence. However, because the shop she bought the strings from is cursed magical, any string she puts on the 🎄 will cause it to collapse if its remainder is not ~K~ modulo ~10^4+7~. How many strings ~X_i~ can rachel decorate her 🎄 with such that it doesn't collapse? Because rachel wants to put many decorations on her 🎄, please give the answer modulo ~10^9+7~.

Input Specification

The first line will contain ~|S|, K\ (1 \le |S|, \le 10^4),\ (0 \le K < 10^4+7)~.

The next line will contain the string ~S~, where ~S~ only contains numeric characters.

Output Specification

Output the number of strings ~X_i~ rachel can put on her 🎄, modulo ~10^9+7~.

Subtasks

Subtask 1 [30%]

~(|S| \le 17)~

Subtask 2 [70%]

No further constraints.

Sample Input

5 3
32123

Sample Output

2

Explanation for Sample

The subsequences in question are ~3~ and ~3~.