Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. The Maths Lecture

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAmr doesn't like Maths as he finds it really boring, so he usually sleeps in Maths lectures. But one day the teacher suspected that Amr is sleeping and asked him a question to make sure he wasn't.

First he gave Amr two positive integers *n* and *k*. Then he asked Amr, how many integer numbers *x* > 0 exist such that:

- Decimal representation of
*x*(without leading zeroes) consists of exactly*n*digits; - There exists some integer
*y*> 0 such that:- ;
- decimal representation of
*y*is a suffix of decimal representation of*x*.

As the answer to this question may be pretty huge the teacher asked Amr to output only its remainder modulo a number *m*.

Can you help Amr escape this embarrassing situation?

Input

Input consists of three integers *n*, *k*, *m* (1 ≤ *n* ≤ 1000, 1 ≤ *k* ≤ 100, 1 ≤ *m* ≤ 10^{9}).

Output

Print the required number modulo *m*.

Examples

Input

1 2 1000

Output

4

Input

2 2 1000

Output

45

Input

5 3 1103

Output

590

Note

A suffix of a string *S* is a non-empty string that can be obtained by removing some number (possibly, zero) of first characters from *S*.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 06:26:40 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|