正の整数の列における「過半数要素（majority element）」とは、その列の要素の半分以上を占める数のことである。

すべての空でない連続部分列が少なくとも1つの過半数要素を持つような列を「良い（good）」列と呼ぶ。例えば、$[1, 2, 1, 1, 3]$ は良い列である。なぜなら、$[1, 1, 3]$、$[1, 2]$、$[2, 1, 1, 3]$ といった部分列はすべて過半数要素を持っているからである。一方、$[1, 2, 1, 3]$ は良い列ではない。なぜなら、$[2, 1, 3]$ は過半数要素を持たないからである。

$1, 2, 3, ?$ からなる文字列が与えられる。各 $?$ を $1, 2, 3$ のいずれかに置き換えて良い列を作る方法の数を求めよ。答えを $10^9 + 7$ で割った余りを出力せよ。

入力

1行目には、文字列の長さである整数 $N$ ($3 \le N \le 200$) が与えられる。 2行目には、$1, 2, 3, ?$ からなる長さ $N$ の文字列が与えられる。

出力

答えを $10^9 + 7$ で割った余りを出力せよ。

小課題

• (10点) $N \le 10$、入力は $?$ のみ。
• (20点) $N \le 25$、入力は $?$ のみ。
• (40点) $N \le 60$。
• (30点) 追加の制約なし。

入出力例

入力 1

3
???

出力 1

21

注記

1つ目の例について、$3^3 = 27$ 通りの配列のうち、良い列ではないものは $[1, 2, 3]$ とその順列のみであるため、答えは $27 - 3! = 21$ となる。

入力 2

3
12?

出力 2

2

注記

2つ目の例について、$[1, 2, 1]$ と $[1, 2, 2]$ は良い列であるが、$[1, 2, 3]$ はそうではない。

入力 3

4
1?11

出力 3

3

注記

3つ目の例について、$[1, 1, 1, 1]$、$[1, 2, 1, 1]$、$[1, 3, 1, 1]$ はすべて良い列である。

入力 4

5
12213

出力 4

0

注記

4つ目の例について、$[1, 2, 2, 1, 3]$ は良い列ではないため、答えは $0$ である。

入力 5

10
???1??????

出力 5

1735