問題文

正整数 $N$, $M$, $D$ が与えられます。 ただし、$D$ は $100$ 以上 $M$ 未満かつ、$M$ の約数です。

次のような条件を満たす、長さ $N$ の数列は何通りあるでしょう？

• 数列の各要素は $1$ 以上 $M - 1$ 以下かつ、$D$ でない整数である
• 数列の要素の総和は $M$ の倍数である

答えを $10^9 + 7$ で割った余りを出力してください。

制約

• $1\leq N\leq 10^{18}$
• $200\leq M\leq 10000$
• $100\leq D < M$
• $M$ は $100$ 以上 $M$ 未満の約数を $1$ つ以上持つ
• $D$ は $M$ の約数である
• 入力はすべて整数である

入力

入力はすべて整数である。

出力

計算結果を一行に出力せよ。

サンプル

1 314 157

0

$N = 1$ の場合は条件を満たす数列は存在しません。

2 200 100

198

$1\leq i\leq 199$ かつ $i\neq 100$ を満たす $i$ を使って $(i, 200 - i)$ と書くことができる数列だけが考えられます。

998244353998244353 9982 161

936931417