問題文
「何度も何度も何度も何度も何度も何度も夏を超えたから...」
正整数a,b,cが与えられます.
また,関数fをf:Z→Z,f(x)=ax2+bx+c,x∈Zで定義します(Zは整数全体の集合を表します).
以下の問いにQ回答えてください.
問iの形式は以下の通りです.
- 問i: 非負整数ni,xiが与えられます.f(ni)(xi)を求めてください.
ここで,f(n)は関数fのn回合成したものを表します.
12/29 22:11追記
この問題では関数の合成回数をf(0)(x)=f(x),f(1)(x)=f(f(x)),f(2)(x)=f(f(f(x)))のように定義します.
詳しくは入出力例を参考にしてください.
答えは非常に大きくなることがあるので,(105+3)で割った余りを出力してください.
制約
- 1≤a,b,c≤109
- 1≤Q≤105
- 0≤ni,xi≤109
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられます.
出力
答えをQ行に出力せよ.i行目には問iの答えを(105+3)で割った余りを出力せよ.
サンプル
入力1
1 2 3
4
0 1
1 1
2 1
3 1
この問題ではf(x)=x2+2x+3です.よって各問の答えは
- f(0)(1)=f(1)=12+2×1+3=6
- f(1)(1)=f(f(1))=62+2×6+3=51
- f(2)(1)=f(f(f(1)))=512+2×51+3=2706
- f(3)(1)=f(f(f(f(1))))=27062+2×2706+3=7327851
となるため,それを(105+3)で割った余りである数値をそれぞれ出力します.