問題文

この問題では，じゃんけんの手「グー」「チョキ」「パー」をそれぞれ \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 点) 追加の制約はない．

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