P14339 [JOI2020 预选赛 R2] 剪刀石头布 / Rock-Scissors-Paper Expression

本题中，将剪刀石头布中的“石头”“剪刀”“布”分别用 $ 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（巴科斯-瑙尔范式），定义如下。其中，表达式中看不清的部分用 `` 表示： ``` ::= | "+" | "-" ::= | "*" ::= "R" | "S" | "P" | "?" | "(" ")" ``` 以上文法的含义是：一个字符串是 ``，当且仅当它是一个 ``，或是一个 ``、字符 `+`、一个 `` 按顺序连接而成，或是一个 ``、字符 `-`、一个 `` 按顺序连接而成。这是一种递归定义。 给定一个长度为 $ N $ 的字符串 $ E $（其中包含若干 `?`），以及目标结果 $ A $，请编写程序，计算将每个 `?` 替换为 $ R $、$ S $、$ P $ 中的任意一个手势后，能使表达式计算结果为 $ A $ 的替换方案总数，并输出该总数对 $ 1\,000\,000\,007 $ 取模的结果。

输入通过标准输入以如下格式给出： $ N $ $ E $ $ A $

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

### 样例 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 $ 是题目中定义的 ``。 - $ A $ 是字符 `'R'`、`'S'` 或 `'P'` 之一。 ### 子任务 1. （20 分）$ N \le 15 $。 2. （20 分）$ N \le 200 $。 3. （60 分）无额外限制。 翻译由 Qwen3-235B 完成