ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## H. Periodic Sum

Time limit: 1.0 second
Memory limit: 64 MB
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(tk) 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(pk)) modulo m.

### Input

The first line contains one integer p (1 ≤ p < 10100000). The second line contains two space-separated integers k and m (1 ≤ k, m ≤ 109).

### Output

Output the answer on a single line.

### Sample

inputoutput
```1205
3 999999999```
`847123538`
Problem Author: Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
To submit the solution for this problem go to the Problem set: 1749. Periodic Sum