Function Composition

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

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

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

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

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

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

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

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

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

1 2 3
4
0 1
1 1
2 1
3 1

6
51
2706
27632

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

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