We define expressions as follows:

• An integer in the range $[0, M-1]$ with no extra leading zeros is an expression.
• If $E$ is an expression, then $(E)$ is an expression.
• If $E_1$ and $E_2$ are expressions, then $E_1+E_2$ and $E_1-E_2$ are expressions.

Given $N, M, P$, you need to find the number of expressions of length $N$ such that their value modulo $M$ is equal to $P$.

Since the answer may be very large, you only need to output the answer modulo $10^9+7$.

Input

The input consists of a single line containing three integers $N, M, P$. It is guaranteed that $0 \leq P < M$.

Output

Output a single integer representing the answer.

Examples

Input 1

3 100 98

Output 1

8

Input 2

50 200 70

Output 2

130371982

Subtasks

For $30\%$ of the data, $N \leq 6$.

For $50\%$ of the data, $N \leq 20, M \leq 50$.

An additional $20\%$ of the data satisfies $M = 2$.

For $100\%$ of the data, $1 \leq N \leq 50, 1 \leq M \leq 200$.