入力

入力は以下の形式で標準入力から与えられる。

a b c

• 1 行目には, a,b,c が空白区切りで与えられる。
• aは数列の長さです。
• bは、数列の初期値に関係する定数です。i番目の要素は、{b}^{i}です。一番左を0番目とします。
• cは、操作をする回数です。

出力

出力は以下の形式で標準出力に従うこと。

• c 回操作をした後の数列の最後の要素の値を1,000,000,007で割った余りを1行に出力してください。

制約

• 1≦a≦100,000
• 1≦b,c≦1,000,000,000

小課題

小課題 1 [ 12 点 ]

• 1≦a,b,c≦1,000 を満たす。

小課題 2 [ 48 点 ]

• 1≦a,b,c≦100,000を満たす。

小課題 3 [ 40 点 ]

• 追加の制約はない。