# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Gifted

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 ≤ 10 ^{4})**,

**MOD(1 ≤ MOD ≤ 10**and

^{9})**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**.