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

在这个问题中，我们将"石头"、"剪刀"、"布"分别用符号 $\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 * y$（注意这并不是我们熟悉的加法、减法和乘法，意义如下）： - $x + y$：当 $x \ne y$ 时，取两个中获胜的一项；如果 $x = y$，则取 $x$。 - $x - y$：当 $x \ne y$ 时，取两个中失败的一项；如果 $x = y$，则取 $x$。 - $x * y$：当 $x \ne y$ 时，取 $\mathrm{R},\ \mathrm{S},\ \mathrm{P}$ 中既非 $x$ 也非 $y$ 的符号；如果 $x = y$，则取 $x$。 表达式由手势符号以及 $+,\ -, *$ 和括号组成，并遵循如下计算规则： - 括号里的内容最优先计算。例如，$\mathrm{R} * (\mathrm{P} + \mathrm{S}) = \mathrm{R} * \mathrm{S} = \mathrm{P}$。 - 在括号深度相同的情况下： - 优先计算 $*$，再计算 $+$ 和 $-$。例如，$\mathrm{R} - \mathrm{P} * \mathrm{S} = \mathrm{R} - (\mathrm{P} * \mathrm{S}) = \mathrm{R} - \mathrm{R} = \mathrm{R}$。 - 对于相同优先级的运算符，例如 $+$ 与 $+$、$-$ 与 $-$、$+$ 与 $-$、$*$ 与 $*$，依照从左到右的顺序计算。例如，$\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 想知道，如何替换这些 `?` 使得整个表达式的运算结果为 $A$ 的方法有多少种。由于方法数可能极大，要求对 $1\,000\,000\,007$ 取模。 表达式由 BNF (巴科斯-诺尔范式) 定义如下： ``` ::= | "+" | "-" ::= | "*" ::= "R" | "S" | "P" | "?" | "(" ")" ``` 这意味着，一个字符串是 <expression>，如果它是 <term>；或者是一个 <expression>，后跟 `+` 和一个 <term> 的组合；或是一个 <expression>，后跟 `-` 和一个 <term> 的组合。 现在给你一个 <expression> 类型的字符串 $E$ 和一个结果 $A$，请编写程序计算以不同方式替换 '?' 所形成的表达式 $E$ 的结果为 $A$ 的方案数，并输出该方案数对 $1\,000\,000\,007$ 取模的结果。

输入以如下形式给出： > $ N $ $ E $ $ A $

输出一个整数，该整数表示将 `?` 替换为 $\mathrm{R},\ \mathrm{S},\ \mathrm{P}$ 中任意一个，使得表达式计算结果为 $A$ 的方案数量，最后需要对 $1\,000\,000\,007$ 取模。

- $1 \leq N \leq 200\,000$。 - $E$ 是长度为 $N$ 的字符串。 - $E$ 是描述中的 <expression>。 - $A$ 是 $\mathrm{R},\ \mathrm{S},\ \mathrm{P}$ 中的一个字符。 ### 子任务 1. （20 分）$N \leq 15$。 2. （20 分）$N \leq 200$。 3. （60 分）无额外限制。 **本翻译由 AI 自动生成**