问题描述

本问题中，将石头剪刀布分别用 $\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 \ne y$ 时，$x + y$ 是 $x$ 和 $y$ 中胜出的那一个；当 $x = y$ 时，$x + y$ 就是 $x$。
• 当 $x \ne y$ 时，$x - y$ 是 $x$ 和 $y$ 中败北的那一个；当 $x = y$ 时，$x - y$ 就是 $x$。
• 当 $x \ne y$ 时，$x \ast y$ 不是 $x$ 也不是 $y$；当 $x = y$ 时，$x \ast y$ 就是 $x$。

石头剪刀布的手势和 $+, -, \ast$ 运算符以及括号构成的表达式可以按以下规则计算：

• 先计算括号内的内容。例如，$\mathrm{R} \ast (\mathrm{P} + \mathrm{S}) = \mathrm{R} \ast \mathrm{S} = \mathrm{P}$。
• 对于同一级别的括号，
  • 优先计算乘法比加减法。例如，$\mathrm{R} - \mathrm{P} \ast \mathrm{S} = \mathrm{R} - (\mathrm{P} \ast \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$，其中 $\mathrm{R}$、$\mathrm{S}$、$\mathrm{P}$ 的一部分被隐藏起来了。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$ 分) 没有额外的约束。

输入

输入从标准输入中提取，具有以下格式。

$N$ $E$ $A$

输出

将表达式的结果设置为 $\mathrm{R}$、$\mathrm{S}$、$\mathrm{P}$ 中的任意字符的方式数目除以 $1,\!000,\!000,\!007$ 后，在标准输出中输出为一行。

输入样例 1

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

输出样例 1

6

有两个 ?，有六种将其分别替换为 $\mathrm{R}$、$\mathrm{S}$、$\mathrm{P}$ 的方法，使得计算结果为 S：

• `$\mathrm{S}$ + $\mathrm{R}$ - ($\mathrm{R}$ + $\mathrm{R}$) * $\mathrm{P}$
• `$\mathrm{S}$ + $\mathrm{R}$ - ($\mathrm{R}$ + $\mathrm{S}$) * $\mathrm{P}$
• `$\mathrm{S}$ + $\mathrm{S}$ - ($\mathrm{R}$ + $\mathrm{R}$) * $\mathrm{P}$
• `$\mathrm{S}$ + $\mathrm{S}$ - ($\mathrm{R}$ + $\mathrm{S}$) * $\mathrm{P}$
• `$\mathrm{S}$ + $\mathrm{P}$ - ($\