問題文

$C$ 個のバス停があり、それぞれバス停 $1$ 、バス停 $2$ 、....、バス停 $C$ と呼ぶことにします,

時刻 $0$ にバス停 $1$ にバスが $M$ 台止まっていて、バス停 $1$ 以外にはバスがいません。

時刻 $i=0,1,2,...,N-1$ に各バス停にいるすべてのバスはそれぞれ以下のように独立に動きます。

• バス停 $x$ にバスがいる場合

• バス停 $x$ 以外のバス停に、それぞれ確率 $\frac{1}{C}$ で時間 $1.5$ かけて移動する

• 確率 $\frac{1}{C}$ でバス停 $x$ にとどまる

時刻 $N$ にバス停 $1$ にバスが1台以上いる確率を $\mathrm{mod}{10}^9+7$ で出力してください。

入力

$CNM$

バス停の数 $C$ と整数 $N$ とバスの数 $M$ が空白区切りで与えられる。

制約

• $2\le C\le 1\times {10}^5$

• $1\le N\le 1\times {10}^9$

• $1\le M\le 1\times {10}^9$

• 入力は全て整数である

サンプル

3 3 1

370370373

10 1 2

830000006