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

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

About     Problems     Submit solution     Judge status     Standings
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