18421번 - じゃんけん式 (Rock-Scissors-Paper Expression) 다국어

この問題では，じゃんけんの手「グー」「チョキ」「パー」をそれぞれ 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 は問題文で定められた である．
• A は `R' または `S' または `P' である．