問題文


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

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

制約


  • 入力は全て整数

入力


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


出力


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

サンプル


入力1
2 6
1 1
出力1
8

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

入力2
2 6
2 1
出力2
11

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

入力3
4 1000
1 2 3 4
出力3
886028826

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

提出


Go (1.14)