F - Range Sum Queries
Editorial
/
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