ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1749. 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