양의 정수 수열의 과반수 원소(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$)이 주어집니다. 두 번째 줄에는 1, 2, 3, 그리고 ?로 구성된 길이 $N$의 문자열이 주어집니다.

출력

정답을 $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]$은 좋은 수열이 아니므로 정답은 0입니다.