Problem Description

In this problem, we represent the rock-paper-scissors hands "rock", "scissors", and "paper" as $\mathrm{R}, \mathrm{S}, \mathrm{P}$ respectively. $\mathrm{R}$ beats $\mathrm{S}$, $\mathrm{S}$ beats $\mathrm{P}$, and $\mathrm{P}$ beats $\mathrm{R}$.

When $ x $ and $ y $ are rock-paper-scissors hands, we define $x + y, x - y, x \ast y$ as follows (these are not the usual arithmetic operations):

• $ x + y $ is the hand that wins between $ x $ and $ y $ if $x \ne y$, and $ x $ if $ x = y $.
• $ x - y $ is the hand that loses between $ x $ and $ y $ if $x \ne y$, and $ x $ if $ x = y $.
• $x \ast y$ is the hand that is neither $ x $ nor $ y $ if $x \ne y$, and $ x $ if $ x = y $.

An expression consisting of rock-paper-scissors hands and the operators $+, -, \ast$ and parentheses is evaluated as follows:

• Evaluate the contents of parentheses first. For example, $\mathrm{R} \ast (\mathrm{P} + \mathrm{S}) = \mathrm{R} \ast \mathrm{S} = \mathrm{P}$.
• For parts with the same depth of parentheses,
• Evaluate $\ast$ before $ +, - $. For example, $\mathrm{R} - \mathrm{P} \ast \mathrm{S} = \mathrm{R} - (\mathrm{P} \ast \mathrm{S}) = \mathrm{R} - \mathrm{R} = \mathrm{R}$.
• For the same precedence ($ + $ with $ + $, $ - $ with $ - $, $ + $ with $ - $, $\ast$ with $\ast$), evaluate from left to right. For example, $\mathrm{R} - \mathrm{P} + \mathrm{S} = (\mathrm{R} - \mathrm{P}) + \mathrm{S} = \mathrm{R} + \mathrm{S} = \mathrm{R}$.

JOI has a certain rock-paper-scissors expression, but some parts of it have become invisible. An expression of length $ N $ with invisible parts represented by ? is given. JOI wants to know how many ways there are to assign $\mathrm{R}, \mathrm{S}, \mathrm{P}$ to the invisible parts such that the expression evaluates to $ A $. Since this number can be very large, he wants the result modulo $1\,000\,000\,007$.

The grammar used in this problem is represented using BNF (Backus-Naur Form) as follows. An expression with some invisible parts is an <expression>.

<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "R" | "S" | "P" | "?" | "(" <expression> ")"

This means, for example, that a string is an <expression> if it is a <term> or a concatenation of an <expression>, +, and a <term>, or a concatenation of an <expression>, -, and a <term>, and so on recursively.

Given a string $ E $ that is an <expression> and a result $ A $, write a program to find the number of ways to assign $\mathrm{R}, \mathrm{S}, \mathrm{P}$ to the ? such that the expression evaluates to $ A $, modulo $1\,000\,000\,007$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ E $ $ A $

Output Format

Output to the standard output the number of ways to assign $\mathrm{R}, \mathrm{S}, \mathrm{P}$ to the ? such that the expression evaluates to $ A $, modulo $1\,000\,000\,007$, in one line.

Sample Input and Output

Sample Input #1

11
S+?-(R+?)*P
S

Sample Output #1

6

Sample Input #2

15
?+?-?*?+?-?*?+?
R

Sample Output #2

2187

Sample Input #3

13
(((((R)))))+?
P

Sample Output #3

1

Sample Input #4

1
P
S

Sample Output #4

0

Sample Input #5

27
R+((?+S-?*P+?)-P*?+S-?)*R+?
P

Sample Output #5

381

Sample Input #6

83
((R+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))-((S+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))
P

Sample Output #6

460353133

Notes/Hints

Constraints

• $1 \leq N \leq 200\,000$.
• $ E $ is a string of length $ N $.
• $ E $ is an <expression> as defined in the problem.
• $ A $ is either R, S, or P.

Subtasks

1. ($ 20 $ points) $N \leq 15$.
2. ($ 20 $ points) $N \leq 200$.
3. ($ 60 $ points) No additional constraints.

Sample Explanation 1

There are 6 ways to assign $\mathrm{R}, \mathrm{S}, \mathrm{P}$ to the two ? such that the expression evaluates to $\mathrm{S}$:
- $\mathrm{S} + \mathrm{R} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}$
- $\mathrm{S} + \mathrm{R} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}$
- $\mathrm{S} + \mathrm{S} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}$
- $\mathrm{S} + \mathrm{S} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}$
- $\mathrm{S} + \mathrm{P} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}$
- $\mathrm{S} + \mathrm{P} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}$

Sample Explanation 6

There are $10\,460\,353\,203$ ways to satisfy the condition, so output $460\,353\,133$, which is the result modulo $1\,000\,000\,007$.

见题面 Input 部分

见题面 Output 部分