Rachel's Christmas Tree

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

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.


Subtask 1 [30%]

(|S| \le 17)

Subtask 2 [70%]

No further constraints.

Sample Input

5 3

Sample Output


Explanation for Sample

The subsequences in question are 3 and 3.


There are no comments at the moment.