가위바위보 표현 timer 1초 memory 1024MB

이 문제에서는, 가위바위보의 손동작 "바위", "가위", "보"를 각각 R, S, P로 나타낸다. R은 S를 이기고, S는 P를 이기며, P는 R을 이긴다.

x, y를 가위바위보의 손동작이라고 할 때, x + y, x - y, x * y를 다음과 같이 정의한다 (이들은 일반적인 의미의 덧셈, 뺄셈, 곱셈이 아니다):

• x + y는, x ≠ y일 때 x와 y 중 승리하는 쪽이며, x = y일 때 x이다.

• x - y는, x ≠ y일 때 x와 y 중 패배하는 쪽이며, x = y일 때 x이다.

• x * y는, x ≠ 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 씨는 어떤 가위바위보 식을 가지고 있었지만, 그 식의 일부가 보이지 않게 되어버렸다. 보이지 않게 된 부분이 ?로 표시된 길이 N의 문자열 E가 주어진다. JOI 씨는, 보이지 않게 된 부분 각각에 R, S, P 중 하나를 할당하는 방법 중에서, 식의 계산 결과가 A가 되는 경우가 몇 개 있는지를 알고 싶어 한다. 그 수는 매우 클 수 있으므로, 1 000 000 007로 나눈 나머지를 구하고자 한다.

이 문제에서 사용되는 문법은, BNF (Backus-Naur Form)로 다음과 같이 표현된다. 가위바위보의 식 일부가 보이지 않게 된 것은 <expression>이다.

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

이는 예를 들어, 어떤 문자열이 <expression>이라는 것은,

• <term>일 수도 있고,

• <expression>인 문자열, +, <term>인 문자열을 이 순서로 연결한 것도 될 수 있으며,

• <expression>인 문자열, -, <term>인 문자열을 이 순서로 연결한 것도 될 수 있다는 것과 같이,
  재귀적으로 정의될 수 있음을 의미한다.