問題文  


すぬけくんはロシア語の筆記体を解読することになりましたが、全ての文字が にみえてしまいました。 ただ、よく見ると、 から成り立つ文字と からなる文字の2種類の文字のみで構成されていることがわかり、文字と文字の区切りにも が使われることがわかりました。 例えば という文字列ならば  の2文字からなることが解読できるようになりました。

いま、 だけからなる長さの文字列 が与えられました。 はロシア語解読の天才すぬけくんにとっても長すぎたので、すぬけくんの代わりにこの元の文字列が解読された結果としてありうるロシア語の文字列が何通りあるか求めてください。 ただし、答えがとても大きくなる場合があるので、代わりに で割った余りを計算してください。

制約


  

ただし は整数

入力


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

N

出力


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

入力例1


2

出力例1


1

の1通りのみです。

入力例2


5

出力例2


2

 と  の2通りです。

入力例3


3141592

出力例3


379555782

答えを で割った余りで出力するのをを忘れないでください。

Submit


Go (1.14)