Note

この問題はHackerRankで公開した自作問題をHackerRank、yukicoder双方の許可を得てこのページに転載しております。

問題文

セルオートマトンというものがあります。
マップをマス目に区切り、全てのマス目はその近傍のマス目の状態によってそのマス目の次の状態が決まるシステムです。
もっともシンプルなセルオートマトンとして1次元のものがあります。
一次元セルオートマトンとは、上段の一列に0と1が並べられ、上段の0と1から次の段の0と1が決定されます。
その中でもマス目の取る値が0と1で、ルール110と呼ばれるものを考えてみましょう。
一次元セルオートマトンルール110を1段目に適用した結果である2段目が与えられますのであり得る1段目の種類数を出力するプログラムを書いてください。
1段目も2段目も右端と左端がつながっており、1段目と2段目の列数は同じだとします。

• 3箇所すべて1なら、0になります。
• 中央と右側が0の場合は、0になります。
• 上記以外は、1になります。

例

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$で割った余りを出力せよ。 最後に改行してください。

サンプル

4
0
0
0
0

2

11
0
1
1
0
1
1
0
1
1
1
0

2

6
1
1
1
1
0
1

3