F - Range Sum Queries

Time Limit: 1 sec / Memory Limit: 128 MB

問題文

数列Aがあります。

A={{b}^{0},{b}^{1},{b}^{2},…,{b}^{a-1}}とします。

c 回, 次のような操作をする。

  • すべての i に対して, A_i= current A_0+A_1+,...+A_iとする。

例えば、a=4,b=3,c=2のとき、次のようになります。

1 3 9 27
1回目 1 4 13 40
2回目 1 5 18 58

一番最後の操作が終わったときのA_{a-1}の値を1,000,000,007で割った余りを出力してください。上の例の場合、答えは58となります。


入力

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

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 点 ]

  • 追加の制約はない。

入力例1

4 3 2

出力例1

58

問題文中の例と同じです。

入力例2

6 1 5

出力例2

252

以下のようになります。

1 1 1 1 1 1
1回目 1 2 3 4 5 6
2回目 1 3 6 10 15 21
3回目 1 4 10 20 35 56
4回目 1 5 15 35 70 126
5回目 1 6 21 56 126 252

入力例3

123 456 789

出力例3

271208111

1,000,000,007で割った余りを求めることに注意してください。

問題文担当者:E869120