AT_s8pc_2_f Range Sum Queries

给定数列$A={{b}^{0}、{b}^{1}、{b}^{2}、…、{b}^{a-1}}$。 进行$c$次操作。 - 对于所有$i$，$A_i$ 表示当前情况下的 $A_0+A_1+，…+A_i$。 答案对 $10^9+7$ 取模。

一行三个整数 $a,b,c$。

一行一个整数表示答案。

### 制約 - $ 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 $で割った余りを求めることに注意してください。