Mary is an intellectually gifted 7-year-old girl. On her first day at school, she impressed her math teacher with her remarkable mathematical talent. As she was far more skilled than any other children of her age, the teacher used to give her harder problems.
One day, the teacher told her to write a large integer having exactly M digits which doesn't contain any leading zeroes. So, Mary wrote an integer N on her notebook. Then her teacher gave her an integer MOD. Mary had to find N % MOD or simply the remainder when N is divided by MOD. Mary was quick in calculation and found the remainder R. Then she gave the notebook to her teacher. Despite being so talented , Mary had a very bad handwriting. Her teacher couldn't identify some of the digits she wrote. As a result, the teacher couldn't figure out whether she did the math right or not.
Can you help the teacher to find out the integer Mary wrote ? If there is exactly one such integer, print it or print the number of such integers.
Input
The first line contains three integers M (1 ≤ M ≤ 104), MOD(1 ≤ MOD ≤ 109) and R(0 ≤ R < MOD).
The second line contains a string N.
Each of the character of the string is either '?' or a digit from '0' to '9'. '?' represents an unidentified digit.
The number of unidentified digits will not exceed 12.
Output
If there are exactly one such integer, print it. Otherwise, print the number of such integers.
Samples
| Input | Output |
|---|---|
2 7 1 2? | 2 |
| Input | Output |
|---|---|
3 79 0 1?? | 158 |
| Input | Output |
|---|---|
2 2 1 ?2 | 0 |
Sample 1 : The possible integers are 22 and 29. So the answer is 2.
Sample 2 : There is only one possible integer , which is 158. So you have to print it.
Sample 3: There exists no possible integer. So the answer is 0.
