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 |
