nnacci sequence

ある数列の先頭項が与えられます。
は下の規則に則っています。

を で割った余りを求めてください。

• 入力は全て整数

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

を で割った余りで出力してください。

2 6
1 1

8

は となるので項目のを出力します。

2 6
2 1

11

は となるので項目のを出力します。

4 1000
1 2 3 4

886028826

で割った余りを出力してください。