問題文

この問題では，じゃんけんの手「グー」「チョキ」「パー」をそれぞれ $\\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> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "R" | "S" | "P" | "?" | "(" <expression> ")"

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

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

制約

• $1 \\leqq N \\leqq 200\\,000$．
• $E$ は長さ $N$ の文字列である．
• $E$ は問題文で定められた である．
• $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$ 行で出力せよ．

---

入力例 1

11
S+?-(R+?)*P
S

出力例 1

6

$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}$

---

入力例 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$ を出力する．