가위바위보식

이 문제에서 가위바위보의 손 「바위」「가위」「보」를 각각 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는 어떤 가위바위보 식을 가지고 있었지만, 그 식 안의 R, S, P의 일부를 볼 수 없게 되었다. 볼 수 없게 된 부분이 ?로 표시된 길이 N의 문자열 E가 주어진다. JOI는 볼 수 없게 된 부분의 각각에 R, S, P 중 하나를 할당하는 방법 중에서 식의 계산 결과가 A가 되는 방법이 몇 가지인지 알고 싶다. 그 수는 매우 커질 수 있으므로 1 000 000 007로 나눈 나머지를 구한다.

이 문제에서 사용되는 문법은 BNF (바커스 표기법)를 사용해 다음과 같이 나타낸다. 가위바위보 식의 일부를 볼 수 없게 된 것은 이다.

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

이는 예를 들어, 어떤 문자열이 이라는 것은 「이다」 또는 「인 문자열, +, 인 문자열을 이 순서로 연결한 것」 또는 「인 문자열, -, 인 문자열을 이 순서로 연결한 것」이라는 식으로 재귀적으로 정의된다는 것을 의미한다.

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

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

N
E
A

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

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