2019 ICPC Asia Danang Regional Contest

Start

2019-12-06 01:20 UTC

2019 ICPC Asia Danang Regional Contest

End

2019-12-06 06:20 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -114 days 12:51:36

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
Counting Palindromes

A palindrome number is a non-negative number without leading zeroes, that reads the same forward or backward. For example, $12321$, $44$ and $9$ are palindrome numbers, while $010$, $123$ and $100$ are not.

Given a positive integer $n$, a prime number $p$ and a non-negative integer $k$ less than $p$. A palindrome number $x$ is called a good palindrome, iff $x$ is equal to $k$ modulo $p$. In other words, the remainder when $x$ is divided by $p$ equals $k$.

Please count the number of good palindromes with exactly $n$ digits. As this number can be very large, please calculate the result modulo $10^9 + 7$.

Input

The input contains $3$ integers $n$, $p$ and $k$ $(1 \le n \le 10^{18}, 2 \le p \le 1\, 000, 0 \le k < p)$. It is guaranteed that $p$ is a prime.

Output

Output a single integer — the number of good palindromes with exactly $n$ digits, modulo $10^9 + 7$.

Explanation of Sample input

The good palindromes are $0$, $2$, $4$, $6$ and $8$.

Sample Input 1 Sample Output 1
1 2 0
5