16:44:54Noteこの問題はHackerRankで公開した自作問題をHackerRank、yukicoder双方の許可を得てこのページに転載しております。問題文セルオートマトンというものがあります。マップをマス目に区切り、全てのマス目はその近傍のマス目の状態によってそのマス目の次の状態が決まるシステムです。シンプルなセルオートマトンとして1次元のものがあります。一次元セルオートマトンとは、上段の一列に0と1が並べられ、上段の0と1から次の段の0と1が決定されます。その中でもマス目の取る値が0と1で、ルール110と呼ばれるものを考えてみましょう。一次元セルオートマトンルール110を1段目に適用した結果である2段目が与えられますのであり得る1段目の種類数を出力するプログラムを書いてください。1段目も2段目も右端と左端がつながっており、1段目と2段目の列数は同じだとします。図は、2段目の計算される箇所だけ注目した、一次元セルオートマトンのルール110の決定ルールの図です。文章で書くと、3箇所すべて1なら、0になります。中央と右側が0の場合は、0になります。上記以外は、1になります。2段目の0と1が1段目の左右中央3つの値から決定されます。1段目から2段目が決定されている。左右がつながってることに注意。00111101入力N$e_1$$\dots$$e_i$$\dots$$e_n$Nは列数である。2000$$e_i$は2段目の$i$列目が0か1どちらかであることを記述している。出力$ans$出力$ans$は2段目を生成できる1段目の種類数を$10^9+7$で割った余りを出力せよ。最後に改行してください。サンプルサンプル1入力40000出力2ありえる1段目は0000か1111しかない。GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。