D. Subarray Majority
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A majority element of a sequence of positive integers is a number equal to at least half of its elements.

Call a sequence good if all of its nonempty contiguous segments have at least one majority element. For example, $$$[1, 2, 1, 1, 3]$$$ is good, since segments such as $$$[1, 1, 3]$$$, $$$[1, 2]$$$, and $$$[2, 1, 1, 3]$$$ all have majority elements, but $$$[1, 2, 1, 3]$$$ is not good because $$$[2, 1, 3]$$$ does not have a majority element.

Given a string consisting of 1, 2, 3, and ?, count the number of ways to form a good sequence of $$$1$$$, $$$2$$$, and $$$3$$$'s by changing each ? to one of $$$1$$$, $$$2$$$, and $$$3$$$. Output the answer modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$N$$$ ($$$3 \le N \le 200$$$), the length of the string.

The second line contains a string of length $$$N$$$, consisting of 1, 2, 3, and ?.

Output

Output the remainder when the answer is divided by $$$10^9 + 7$$$.

Scoring
  • (10 points) $$$N \le 10$$$, the input contains only ?'s.
  • (20 points) $$$N \le 25$$$, the input contains only ?'s.
  • (40 points) $$$N \le 60$$$.
  • (30 points) No additional constraints.
Examples
Input
3
???
Output
21
Input
3
12?
Output
2
Input
4
1?11
Output
3
Input
5
12213
Output
0
Input
10
???1??????
Output
1735
Note

For the first sample, the only arrays (out of $$$3^3 = 27$$$ possible ones) that are not good are $$$[1, 2, 3]$$$ and its permutations, so the answer is $$$27 - 3! = 21$$$.

For the second sample, $$$[1, 2, 1]$$$ and $$$[1, 2, 2]$$$ are good, but not $$$[1, 2, 3]$$$.

For the third sample, $$$[1, 1, 1, 1]$$$, $$$[1, 2, 1, 1]$$$, and $$$[1, 3, 1, 1]$$$ are all good.

For the fourth sample, since $$$[1, 2, 2, 1, 3]$$$ is not good, the answer is zero.