問題文

$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台以上いる確率を $\mod 10^9+7$ で出力してください。

確率を $\mod 10^9+7$ で出力するとは (クリックで開きます)

確率を既約分数 $\frac{P}{Q}$ で表したとき、 $R\times Q=P (mod 10^9+7)$ を満たし、かつ $0≤R<10^9+7$ を満たす 非負整数 $R$ を出力してください。

入力

$C\ N\ M$

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

制約

• $2≤C≤1\times10^5$

• $1≤N≤1\times10^9$

• $1≤M≤1\times10^9$

• 入力は全て整数である

サンプル