Problem E
Report Card

After coming to college from high school, you discovered something absolutely tragic. The way that GPA is calculated is completely different than what you are used to. Apparently, pluses and minuses are treated very differently than they were before, according to the following table.

Figure 1: Grade Point Table Comparing High School Against UCLA

GPA is calculated by taking the sum of the individual grade points (seen in the table above) and dividing it by the number of courses. You have received your report card for the current quarter, but you’ve blocked out the pluses and minuses instead because you’re too scared to look, so your report card can be one of many different variations. For example, a report card of ABB could be A+ B B+, A- B- B+, or even A B B. In how many possible report card variations will the college grading system actually be better for your GPA compared to your old high school system? Since this number might be quite large, print out your answer modulo $10^9+7$. Note that order matters, so A B B+ and A B+ B are considered two different variations of ABB.

Input

The input starts with one line containing an integer $N$, denoting the length of the report card ($1 \leq N \leq 3\, 000$).

The second line is a string of $N$ characters (A,B,C,D,F) representing the obscured report card.

Output

The number of report cards modulo $10^9+7$ that would give you a strictly better GPA than in high school.

2
AB

2

3
CCF

3