AT_s8pc_2_f Range Sum Queries

[problemUrl]: https://atcoder.jp/contests/s8pc-2/tasks/s8pc_2_f 数列$ 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 $ 点 \] - 追加の制約はない。 ### Sample Explanation 1 問題文中の例と同じです。 ### Sample Explanation 2 以下のようになります。 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 ### Sample Explanation 3 $ 1,000,000,007 $で割った余りを求めることに注意してください。