题目描述

本题中，将剪刀石头布中的“石头”“剪刀”“布”分别用 $R$、$S$、$P$ 表示。规则为：$R$ 胜 $S$，$S$ 胜 $P$，$P$ 胜 $R$。

当 $x$、$y$ 为剪刀石头布的手势时，定义 $x + y$、$x - y$、$x * y$ 如下（注意：这些运算并非通常意义下的加法、减法、乘法）：

• $x + y$：当 $x \ne y$ 时，结果为 $x$ 与 $y$ 中的胜者；当 $x = y$ 时，结果为 $x$。
• $x - y$：当 $x \ne y$ 时，结果为 $x$ 与 $y$ 中的败者；当 $x = y$ 时，结果为 $x$。
• $x * y$：当 $x \ne y$ 时，结果为 $R$、$S$、$P$ 中既不是 $x$ 也不是 $y$ 的那个手势；当 $x = y$ 时，结果为 $x$。

由剪刀石头布手势与 $+$、$-$、$*$ 以及括号组成的表达式，按以下规则计算：

• 先计算括号内的表达式。例如，$R * (P + S) = R * S = P$。
• 对于相同层级的括号部分：
  • 优先计算 $*$，再计算 $+$ 和 $-$。例如，$R - P * S = R - (P * S) = R - R = R$。
  • 对于优先级相同的运算符（如 $+$ 与 $+$、$-$ 与 $-$、$+$ 与 $-$、$*$ 与 $*$），按从左到右的顺序计算。例如，$R - P + S = (R - P) + S = R + S = R$。

JOI 先生原本持有一个剪刀石头布表达式，但其中部分 $R$、$S$、$P$ 已经看不清了。已知看不清的部分由字符 ? 表示，且整个表达式长度为 $N$。JOI 先生想知道，将每个 ? 替换为 $R$、$S$、$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> 按顺序连接而成。这是一种递归定义。

给定一个长度为 $N$ 的字符串 $E$（其中包含若干 ?），以及目标结果 $A$，请编写程序，计算将每个 ? 替换为 $R$、$S$、$P$ 中的任意一个手势后，能使表达式计算结果为 $A$ 的替换方案总数，并输出该总数对 $1\,000\,000\,007$ 取模的结果。

输入格式

输入通过标准输入以如下格式给出：

$N$

$E$

$A$

输出格式

在标准输出中，输出一行，表示将每个 ? 替换为 $R$、$S$、$P$ 中的任意一个手势后，能使表达式计算结果等于 $A$ 的方案总数，对 $1\,000\,000\,007$ 取模的结果。

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

6

15
?+?-?*?+?-?*?+?
R

2187

13
(((((R)))))+?
P

1

1
P
S

0

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

381

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

460353133

提示

样例 1 解释

将两个 ? 分别替换为 $R$、$S$、$P$ 中的任意一个手势，使得表达式计算结果为 $S$ 的方法共有以下 6 种：

• $S + R - (R + R) * P$
• $S + R - (R + S) * P$
• $S + S - (R + R) * P$
• $S + S - (R + S) * P$
• $S + P - (R + R) * P$
• $S + P - (R + S) * P$

数据范围

• $1 \le N \le 200\,000$。
• $E$ 是长度为 $N$ 的字符串。
• $E$ 是题目中定义的 <expression>。
• $A$ 是字符 'R'、'S' 或 'P' 之一。

子任务

1. （20 分）$N \le 15$。
2. （20 分）$N \le 200$。
3. （60 分）无额外限制。

翻译由 Qwen3-235B 完成