じゃんけん式 (Rock-Scissors-Paper Expression)

この問題では,じゃんけんの手「グー」「チョキ」「パー」をそれぞれ R, S, P で表す. R は S に勝ち, S は P に勝ち, P は R に勝つ.

x, y をじゃんけんの手とするとき, x + y, x - y, x * y を以下のように定める (これらは通常の意味での足し算・引き算・掛け算ではない):

x + y は, \(x \ne y\) のとき x と y のうち勝つ方とし, x = y のとき x とする.

x - y は, \(x \ne y\) のとき x と y のうち負ける方とし, x = y のとき x とする.

x * y は, \(x \ne 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 ≦ N ≦ 200 000 .

E は長さ N の文字列である.

E は問題文で定められた である.

A は R' またはS' または `P' である.

( 20 点) N ≦ 15 .

( 20 点) N ≦ 200 .

( 60 点) 追加の制約はない.

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

N

E

A

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

생성자가 기록되지 않았습니다.

출처 JOI 2020 Preliminary 2