시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 2 2 100.000%

문제

この問題では,じゃんけんの手「グー」「チョキ」「パー」をそれぞれ 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 (バッカス・ナウア記法) を用いて以下のように表される.じゃんけんの式の一部が見えなくなってしまったものは <expression> である.

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

これは例えば,ある文字列が <expression> であるとは,「<term> である」または「<expression> である文字列,`+',<term> である文字列,をこの順に連結させたもの」または「<expression> である文字列,`-',<term> である文字列,をこの順に連結させたもの」であることである,というように再帰的に定義されることを意味する.

<expression> である文字列 E と計算結果 A が与えられるので,`?' に R, S, P のいずれかを割り当てる方法であって式の計算結果が A になるものの個数を 1 000 000 007 で割った余りを求めるプログラムを作成せよ.

입력

入力は以下の形式で標準入力から与えられる.

N
E
A

출력

標準出力に,`?' に R, S, P のいずれかを割り当てる方法であって式の計算結果が A になるものの個数を 1 000 000 007 で割った余りを 1 行で出力せよ.

제한

  • 1 ≦ N ≦ 200 000
  • E は長さ N の文字列である.
  • E は問題文で定められた <expression> である.
  • A は `R' または `S' または `P' である.

예제 입력 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 を出力する.