Let *S*(*t*) be the sum of integers represented by all substrings of the decimal representation of *t*.
For example, *S*(1205) = 1 + 2 + 0 + 5 + 12 + 20 + 05 + 120 + 205 + 1205 = 1575.
Note that some substrings can have leading zeros. Let *F*(*t*, *k*) be the number which decimal representation is obtained by repeating
the decimal representation of *t* *k* times.
For example, *F*(1205, 3) = 120512051205.
Given numbers *p*, *k* and *m*, calculate *S*(*F*(*p*, *k*)) modulo *m*.

### Input

The first line contains one integer *p* (1 ≤ *p* < 10^{100000}). The second line contains two space-separated integers *k* and *m* (1 ≤ *k*, *m* ≤ 10^{9}).

### Output

Output the answer on a single line.

### Sample

input | output |
---|

1205
3 999999999 | 847123538 |

**Problem Author: **Petr Lezhankin

**Problem Source: **Ufa SATU Contest. Petrozavodsk Summer Session, August 2009