Một phần tử đa số của một dãy các số nguyên dương là một số xuất hiện ít nhất một nửa số lần trong dãy đó.

Một dãy được gọi là tốt nếu tất cả các đoạn con liên tiếp không rỗng của nó đều có ít nhất một phần tử đa số. Ví dụ, $[1, 2, 1, 1, 3]$ là một dãy tốt, vì các đoạn như $[1, 1, 3]$, $[1, 2]$ và $[2, 1, 1, 3]$ đều có phần tử đa số, nhưng $[1, 2, 1, 3]$ không phải là dãy tốt vì đoạn $[2, 1, 3]$ không có phần tử đa số.

Cho một chuỗi bao gồm các ký tự 1, 2, 3 và ?, hãy đếm số cách tạo thành một dãy tốt gồm các số 1, 2 và 3 bằng cách thay thế mỗi dấu ? bằng một trong các số 1, 2 hoặc 3. Hãy in ra kết quả theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$ ($3 \le N \le 200$), độ dài của chuỗi. Dòng thứ hai chứa một chuỗi có độ dài $N$, bao gồm các ký tự 1, 2, 3 và ?.

Dữ liệu ra

In ra phần dư của kết quả khi chia cho $10^9 + 7$.

Nhiệm vụ con

• (10 điểm) $N \le 10$, đầu vào chỉ chứa các dấu ?.
• (20 điểm) $N \le 25$, đầu vào chỉ chứa các dấu ?.
• (40 điểm) $N \le 60$.
• (30 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

3
???

21

Ví dụ 2

3
12?

2

Ví dụ 3

4
1?11

3

Ví dụ 4

5
12213

0

Ví dụ 5

10
???1??????

1735

Ghi chú

Với ví dụ đầu tiên, các mảng duy nhất (trong số $3^3 = 27$ khả năng) không phải là dãy tốt là $[1, 2, 3]$ và các hoán vị của nó, vì vậy kết quả là $27 - 3! = 21$.

Với ví dụ thứ hai, $[1, 2, 1]$ và $[1, 2, 2]$ là các dãy tốt, nhưng $[1, 2, 3]$ thì không.

Với ví dụ thứ ba, $[1, 1, 1, 1]$, $[1, 2, 1, 1]$ và $[1, 3, 1, 1]$ đều là các dãy tốt.

Với ví dụ thứ tư, vì $[1, 2, 2, 1, 3]$ không phải là dãy tốt, nên kết quả là 0.