すぬけくんはロシア語の筆記体を解読することになりましたが、全ての文字が にみえてしまいました。 ただ、よく見ると、 から成り立つ文字と からなる文字の2種類の文字のみで構成されていることがわかり、文字と文字の区切りにも が使われることがわかりました。 例えば という文字列ならば の2文字からなることが解読できるようになりました。
いま、 だけからなる長さの文字列 が与えられました。 はロシア語解読の天才すぬけくんにとっても長すぎたので、すぬけくんの代わりにこの元の文字列が解読された結果としてありうるロシア語の文字列が何通りあるか求めてください。 ただし、答えがとても大きくなる場合があるので、代わりに で割った余りを計算してください。
ただし は整数
入力は以下の形式で標準入力から与えられる。
N
答えを で割った余りを出力してください
2
1
の1通りのみです。
5
2
と の2通りです。
3141592
379555782
答えを で割った余りで出力するのをを忘れないでください。