가위바위보 식

문제

이 문제에서는, 가위바위보의 수 「바위」 「가위」 「보」 를 각각 R, S, P 로 나타낸다. R 은 S 를 이기고, S 는 P 를 이기고, P 는 R 을 이긴다.

$x, y$ 를 가위바위보의 수라고 할 때, $x + y,\,\, x - y,\,\, x * y$ 를 다음과 같이 정한다 (이것들은 통상적인 의미에서의 덧셈·뺄셈·곱셈이 아니다):

• $x + y$ 는, $x \neq y$ 일 때 $x$ 와 $y$ 중 이기는 쪽으로 하고, $x = y$ 일 때 $x$ 로 한다.
• $x - y$ 는, $x \neq y$ 일 때 $x$ 와 $y$ 중 지는 쪽으로 하고, $x = y$ 일 때 $x$ 로 한다.
• $x * y$ 는, $x \neq y$ 일 때 R, S, P 중 $x$ 도 $y$ 도 아닌 것으로 하고, $x = y$ 일 때 $x$ 로 한다.

가위바위보의 수와 $+, -, *$ 와 괄호로 이루어진 식은, 다음과 같이 계산한다:

• 괄호 안을 먼저 계산한다. 예를 들어, R * (P + S) = R * S = P 이다.
• 괄호의 깊이가 같은 부분에 대해서는, $+, -$ 보다 $*$ 를 우선하여 계산한다. 예를 들어, R - P * S = R - (P * S) = R - R = R 이다. 우선순위가 같은 것 ($+$ 끼리, $-$ 끼리, $+$ 와 $-$, $*$ 끼리) 에 대해서는, 왼쪽부터 순서대로 계산한다. 예를 들어, R - P + S = (R - P) + S = R + S = R 이다.

JOI 씨는 어떤 가위바위보 식을 가지고 있었는데, 그 식 안의 R, S, P 의 일부가 보이지 않게 되어 버렸다. 보이지 않게 된 부분이 `?' 로 표시된 길이 $N$ 의 문자열 $E$ 가 주어진다. JOI 씨는, 보이지 않게 된 부분 각각에 R, S, P 중 하나를 할당하는 방법으로서 식의 계산 결과가 $A$ 가 되는 것이 몇 가지인지 알고 싶다. 그 수는 매우 커질 가능성이 있으므로, $1 000 000 007$ 로 나눈 나머지를 구하고자 한다.

본 문제에서 사용되는 문법은, BNF (배커스-나우어 표기법) 를 사용하여 다음과 같이 표현된다. 가위바위보 식의 일부가 보이지 않게 된 것은 이다.

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

이것은 예를 들어, 어떤 문자열이 이라는 것은, 「 이다」 또는 「 인 문자열, +', <term> 인 문자열, 을 이 순서로 연결한 것」 또는 「<expression> 인 문자열, -', 인 문자열, 을 이 순서로 연결한 것」 이라는 것이다, 와 같이 재귀적으로 정의됨을 의미한다.

인 문자열 $E$ 와 계산 결과 $A$ 가 주어질 때, `?' 에 R, S, P 중 하나를 할당하는 방법으로서 식의 계산 결과가 $A$ 가 되는 것의 개수를 $1 000 000 007$ 로 나눈 나머지를 구하는 프로그램을 작성하시오.

제한

• $1 \le N \le 200 000$.
• $E$ 는 길이 $N$ 의 문자열이다.
• $E$ 는 문제문에서 정해진 이다.
• $A$ 는 R' 또는 S' 또는 `P' 이다.

서브태스크

1. ($20$ 점) $N \le 15$.
2. ($20$ 점) $N \le 200$.
3. ($60$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$
$E$
$A$

출력

표준 출력에, `?' 에 R, S, P 중 하나를 할당하는 방법으로서 식의 계산 결과가 $A$ 가 되는 것의 개수를 $1 000 000 007$ 로 나눈 나머지를 $1$ 줄에 출력한다.

예제 입력 1

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

예제 출력 1

6

$2$ 군데의 `?' 에 R, S, P 중 하나를 할당하여 계산 결과를 S 로 만드는 방법은, 다음 $6$ 가지가 있다:

• S + R - (R + R) * P
• S + R - (R + S) * P
• S + S - (R + R) * P
• S + S - (R + S) * P
• S + P - (R + R) * P
• S + P - (R + S) * P

예제 입력 2

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

예제 출력 2

2187

예제 입력 3

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

예제 출력 3

1

예제 입력 4

1
P
S

예제 출력 4

0

예제 입력 5

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

예제 출력 5

381

예제 입력 6

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

예제 출력 6

460353133

조건을 만족하는 할당 방법은 $10 460 353 203$ 가지이므로, 그것을 $1 000 000 007$ 로 나눈 나머지인 $460 353 133$ 을 출력한다.