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

[problemUrl]: https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_e この問題では，じゃんけんの手「グー」「チョキ」「パー」をそれぞれ $ \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> である． ``` ::= | "+" | "-" ::= | "*" ::= "R" | "S" | "P" | "?" | "(" ")" ``` これは例えば，ある文字列が <expression> であるとは，「<term> である」または「<expression> である文字列，`+`，<term> である文字列，をこの順に連結させたもの」または「<expression> である文字列，`-`，<term> である文字列，をこの順に連結させたもの」であることである，というように再帰的に定義されることを意味する． <expression> である文字列 $ E $ と計算結果 $ A $ が与えられるので，`?` に $ \mathrm{R},\ \mathrm{S},\ \mathrm{P} $ のいずれかを割り当てる方法であって式の計算結果が $ A $ になるものの個数を $ 1\,000\,000\,007 $ で割った余りを求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ E $ $ A $

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

### 制約 - $ 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 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 2 $ 箇所の `?` に $ \mathrm{R},\ \mathrm{S},\ \mathrm{P} $ のいずれかを割り当てて計算結果を $ \mathrm{S} $ にする方法は，以下の $ 6 $ 通りがある： - $ \mathrm{S}\ +\ \mathrm{R}\ -\ (\mathrm{R}\ +\ \mathrm{R})\ \ast\ \mathrm{P} $ - $ \mathrm{S}\ +\ \mathrm{R}\ -\ (\mathrm{R}\ +\ \mathrm{S})\ \ast\ \mathrm{P} $ - $ \mathrm{S}\ +\ \mathrm{S}\ -\ (\mathrm{R}\ +\ \mathrm{R})\ \ast\ \mathrm{P} $ - $ \mathrm{S}\ +\ \mathrm{S}\ -\ (\mathrm{R}\ +\ \mathrm{S})\ \ast\ \mathrm{P} $ - $ \mathrm{S}\ +\ \mathrm{P}\ -\ (\mathrm{R}\ +\ \mathrm{R})\ \ast\ \mathrm{P} $ - $ \mathrm{S}\ +\ \mathrm{P}\ -\ (\mathrm{R}\ +\ \mathrm{S})\ \ast\ \mathrm{P} $ ### Sample Explanation 6 条件を満たす割り当て方は $ 10\,460\,353\,203 $ 通りあるため，それを $ 1\,000\,000\,007 $ で割った余りである $ 460\,353\,133 $ を出力する．