题目描述
我们如下定义表达式：
- 一个在 $[0,M-1]$ 内且没有多余前导零的整数是一个表达式
- 若 $E$ 是一个表达式，则 $(E)$ 是一个表达式
- 若 $E_1,E_2$ 是一个表达式，则 $E_1+E_2$ 和 $E_1-E_2$ 都是表达式
现在给定 $N,M,P$，你需要求有多少个长度为 $N$ 的表达式满足它的值模 $M$ 等于 $P$
由于答案可能非常大，你只需要输出答案对 $10^9+7$ 取模后的值
输入格式
输入只有一行，包含三个整数 $N,M,P$。保证 $0 \leq M < P$。
输出格式
输出一行一个整数，表示答案。
样例数据
样例 1 输入
3 100 98样例 1 输出
8样例 2 输入
50 200 70样例 2 输出
130371982子任务
对于 $30\%$ 的数据，$N \leq 6$。
对于 $50\%$ 的数据，$N \leq 20, M \leq 50$。
另有 $20\%$ 的数据，$M = 2$。
对于 $100\%$ 的数据，$1 \leq N \leq 50, 1 \leq M \leq 200$。