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

この問題では，じゃんけんの手「グー」「チョキ」「パー」をそれぞれ \(\mathrm{R}, \mathrm{S}, \mathrm{P}\) で表す．\(\mathrm{R}\) は \(\mathrm{S}\) に勝ち，\(\mathrm{S}\) は \(\mathrm{P}\) に勝ち，\(\mathrm{P}\) は \(\mathrm{R}\) に勝つ．

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

• \(x + y\) は，\(x \ne y\) のとき \(x\) と \(y\) のうち勝つ方とし，\(x = y\) のとき \(x\) とする．
• \(x - y\) は，\(x \ne y\) のとき \(x\) と \(y\) のうち負ける方とし，\(x = y\) のとき \(x\) とする．
• \(x \ast y\) は，\(x \ne y\) のとき \(\mathrm{R}, \mathrm{S}, \mathrm{P}\) のうち \(x\) でも \(y\) でもないものとし，\(x = y\) のとき \(x\) とする．

じゃんけんの手と \(+, -, \ast\) と括弧からなる式は，以下のように計算する：

• 括弧の中は先に計算する．例えば，\(\mathrm{R} \ast (\mathrm{P} + \mathrm{S}) = \mathrm{R} \ast \mathrm{S} = \mathrm{P}\) である．
• 括弧の深さが同じ部分については，
  • \(+, -\) より \(\ast\) の方を優先して計算する．例えば，\(\mathrm{R} - \mathrm{P} \ast \mathrm{S} = \mathrm{R} - (\mathrm{P} \ast \mathrm{S}) = \mathrm{R} - \mathrm{R} = \mathrm{R}\) である．
  • 同じ優先順位のもの (\(+\) どうし，\(-\) どうし，\(+\) と \(-\)，\(\ast\) どうし) については，左から順番に計算する．例えば，\(\mathrm{R} - \mathrm{P} + \mathrm{S} = (\mathrm{R} - \mathrm{P}) + \mathrm{S} = \mathrm{R} + \mathrm{S} = \mathrm{R}\) である．

JOI さんはあるじゃんけんの式を持っていたが，その式の中の \(\mathrm{R}, \mathrm{S}, \mathrm{P}\) の一部が見えなくなってしまった．見えなくなってしまった部分が ? で表された長さ \(N\) の文字列 \(E\) が与えられる．JOI さんは，見えなくなってしまった部分のそれぞれに \(\mathrm{R}, \mathrm{S}, \mathrm{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\) が与えられるので，? に \(\mathrm{R}, \mathrm{S}, \mathrm{P}\) のいずれかを割り当てる方法であって式の計算結果が \(A\) になるものの個数を \(1\,000\,000\,007\) で割った余りを求めるプログラムを作成せよ．

• \(1 \leqq N \leqq 200\,000\)．
• \(E\) は長さ \(N\) の文字列である．
• \(E\) は問題文で定められた <expression> である．
• \(A\) は R または S または P である．

1. (\(20\) 点) \(N \leqq 15\)．
2. (\(20\) 点) \(N \leqq 200\)．
3. (\(60\) 点) 追加の制約はない．

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

\(N\)
\(E\)
\(A\)

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

JOI 2020 · JCIOI · CC BY-SA 4.0