Rock-Scissors-Paper Expression

Time limit2sMemory limit512 MB

Summary

Count the assignments of R, S, P to the ? symbols in a fixed arithmetic expression, under rock-scissors-paper defined operators, so that evaluation gives A.

Level: Hard8 of 10
Topics: Dynamic programming, Divide and conquer, Stack, Math
Solved: No attempts yet

Problem

In this problem, the rock-scissors-paper hands "rock", "scissors", and "paper" are represented by R, S, and P respectively. R beats S, S beats P, and P beats R.

For rock-scissors-paper hands x and y, define x + y, x - y, and x * y as follows (these are not ordinary addition, subtraction, and multiplication).

x + y is the winner among x and y when x ≠ y, and is x when x = y.
x - y is the loser among x and y when x ≠ y, and is x when x = y.
x * y is the hand among R, S, P that is neither x nor y when x ≠ y, and is x when x = y.

An expression consisting of rock-scissors-paper hands, +, -, *, and parentheses is evaluated as follows.

Parentheses are evaluated first. For example, R * (P + S) = R * S = P.
For parts at the same parenthesis depth,
- - is evaluated before + and -. For example, R - P * S = R - (P * S) = R - R = R.
- Operators with the same precedence (among +, among -, + with -, among *) are evaluated from left to right. For example, R - P + S = (R - P) + S = R + S = R.

JOI had a certain rock-scissors-paper expression, but some of the R, S, and P in that expression became invisible. A string E of length N is given, in which the invisible parts are denoted by ?. JOI wants to know how many ways there are to assign one of R, S, P to each invisible part so that the result of evaluating the expression equals A. Since the number may be very large, find it modulo 1 000 000 007.

The grammar used in this problem is expressed using BNF (Backus-Naur Form) as follows. A rock-scissors-paper expression with some parts invisible is an .

::= | "+" | "-" ::= | "*" ::= "R" | "S" | "P" | "?" | "(" ")"

For example, this means that a string is an if it is a , or is a string that is an , followed by +, followed by a string that is a , or is a string that is an , followed by -, followed by a string that is a , defined recursively in this way.

Given a string E that is an and an evaluation result A, write a program that finds the number of ways to assign one of R, S, P to each ? so that the result of evaluating the expression equals A, modulo 1 000 000 007.

Input

Input is given from standard input in the following format.

N
E
A

Output

On standard output, print in one line the number of ways to assign one of R, S, P to each ? so that the result of evaluating the expression equals A, modulo 1 000 000 007.

Constraints

1 ≦ N ≦ 200 000.
E is a string of length N.
E is an as defined in the problem statement.
A is R, S, or P.

Examples5

Example 1
Input
```
11
S+?-(R+?)*P
S
```
Expected output
```
6
```
Example 2
Input
```
15
?+?-?*?+?-?*?+?
R
```
Expected output
```
2187
```
Example 3
Input
```
13
(((((R)))))+?
P
```
Expected output
```
1
```
Example 4
Input
```
1
P
S
```
Expected output
```
0
```
Example 5
Input
```
27
R+((?+S-?*P+?)-P*?+S-?)*R+?
P
```
Expected output
```
381
```