Function Composition

2 secs 1024 MB
RedSpica

問題文


「何度も何度も何度も何度も何度も何度も夏を超えたから...」

正整数が与えられます. また,関数で定義します(は整数全体の集合を表します).

以下の問いに回答えてください. 問の形式は以下の通りです.

  • 非負整数が与えられます.を求めてください. ここで,は関数回合成したものを表します.

12/29 22:11追記
この問題では関数の合成回数をのように定義します. 詳しくは入出力例を参考にしてください.

答えは非常に大きくなることがあるので,で割った余りを出力してください.

制約


  • 入力される値はすべて整数である

入力


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






出力


答えを行に出力せよ.行目には問の答えをで割った余りを出力せよ.

サンプル


入力1
1 2 3
4
0 1
1 1
2 1
3 1
出力1
6
51
2706
27632

この問題ではです.よって各問の答えは

となるため,それをで割った余りである数値をそれぞれ出力します.

提出


Go (1.14)