No.663 セルオートマトンの逆操作

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 36
作問者 : horiesinitihoriesiniti / テスター : はむこはむこ
1 ProblemId : 1955 / 出題時の順位表

Note

この問題は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段目の例。 1段目から2段目が決定されている。 左右がつながってることに注意。

1段目 00010111

2段目 00111101

入力

N
$e_1$
$\dots$
$e_i$
$\dots$
$e_n$

Nは列数である。 $4 \le N \le 2000$
$e_i$は2段目の$i$列目が0か1どちらかであることを記述している。

出力

$ans$
出力$ans$は2段目を生成できる1段目の種類数を$10^9+7$で割った余りを出力せよ。 最後に改行してください。

サンプル

サンプル1
入力
4
0
0
0
0
出力
2

ありえる1段目は0000か1111しかない。

サンプル2
入力
11
0
1
1
0
1
1
0
1
1
1
0
出力
2

サンプル3
入力
6
1
1
1
1
0
1
出力
3

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。