一個正整數數列的「多數元素」（majority element）是指一個出現次數至少佔該數列元素總數一半的數字。

若一個數列的所有非空連續子段都至少包含一個多數元素，則稱該數列為「好的」（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$ 取模後的結果。

輸入格式

第一行包含一個整數 $N$ ($3 \le N \le 200$)，代表字串的長度。 第二行包含一個長度為 $N$ 的字串，由 $1, 2, 3$ 和 $?$ 組成。

輸出格式

輸出答案對 $10^9 + 7$ 取模後的餘數。

子任務

• (10 分) $N \le 10$，輸入僅包含 $?$。
• (20 分) $N \le 25$，輸入僅包含 $?$。
• (40 分) $N \le 60$。
• (30 分) 無額外限制。

範例

輸入 1

3
???

輸出 1

21

輸入 2

3
12?

輸出 2

2

輸入 3

4
1?11

輸出 3

3

輸入 4

5
12213

輸出 4

0

輸入 5

10
???1??????

輸出 5

1735

說明

對於第一個範例，在 $3^3 = 27$ 種可能的陣列中，唯一不是「好的」陣列是 $[1, 2, 3]$ 及其排列，因此答案為 $27 - 3! = 21$。

對於第二個範例，$[1, 2, 1]$ 和 $[1, 2, 2]$ 是好的，但 $[1, 2, 3]$ 不是。

對於第三個範例，$[1, 1, 1, 1]$、$[1, 2, 1, 1]$ 和 $[1, 3, 1, 1]$ 皆為好的。

對於第四個範例，由於 $[1, 2, 2, 1, 3]$ 不是好的，因此答案為零。