配点: 100 点
問題文
在这个问题中,剪刀石头布的动作“goo”、“choki”和“pa”分别是 由 \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> ")"
例如,说一个字符串是一个<表达式>意味着它是一个<术语>,或者说一个字符串是一个<表达式>,+,<term> 的字符串,按此顺序连接”或“<表达式> 的字符串,-、 <term> 按此顺序连接,依此类推。
一个字符串,即 <表达式> 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。
小課題
- (20 点) N \leqq 15.
- (20 点) N \leqq 200.
- (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 。 你只需要砍掉