イクタ君は速いプログラムが大好きである。最近は、除算のプログラムを高速にしようとしている。しかしなかなか速くならないので、「常識的に考えて典型的」な入力に対してのみ高速にすればよいと考えた。イクタ君が解こうとしている問題は次のようなものである。
与えられた非負整数nに対し、10進法でp(n) − 1桁の正整数11...1をp(n)で割ったあまりを求めよ。ただしp(n)は22{ . . . 2}(2がn個)より大きい最小の素数を表すとする。p(0) = 2とする。
あなたの仕事は、イクタ君より速くプログラムを完成させることである。
入力は以下の形式で与えられる。
n
問題の入力の非負整数nがあたえられる。
入力中の各変数は以下の制約を満たす。
問題の解を1行に出力せよ。
0
1
1
2
2
1