[ARC175] A - Spoon Taking Problem

A - Spoon Taking Problem

Time Limit: 2 sec / Memory Limit: 1024 MB

题面

个人坐在一个圆桌周围，依次编号为 到 ，顺时针排列。每个人都有一个主导手：左手或右手。

圆桌上有 把勺子，编号为 到 ，每两个相邻的人之间放一把勺子。对于每个 ，在第 个人的左边和右边，分别有编号为 和 的勺子。这里，勺子 表示勺子 。

下面是 时的示意图。

给定一个 的排列 。按顺序 ，第 个人将会按照以下方式行动：

• 如果左边或右边还有剩余的勺子，他们会拿一把。
  • 如果两边都还有勺子，他们会拿主导手所在的那一边的勺子。
• 否则，他们不做任何事情。

同时给定一个长度为 的字符串 ，由 L、R 和 ? 组成。在满足以下条件的所有 种可能的主导手组合中，找出有多少种满足条件，结果对 取模：

• 如果 的第 个字符是 L，则第 个人是左撇子。
• 如果 的第 个字符是 R，则第 个人是右撇子。
• 当每个人完成行动后，每个人都拿了一把勺子。

限制条件

• 所有输入值都是整数。
• 是 的一个排列。
• 是一个由 L、R 和 ? 组成的长度为 的字符串。

---

输入

输入以以下格式从标准输入给出：

输出

在一行中输出答案。

---

输入样例 1

3
1 2 3
L??

输出样例 1

2

当第 个人是左撇子，第 个人是左撇子，第 个人是右撇子时，行动如下：

• 第 个人开始行动。两边都有勺子，所以他拿左边的勺子 ，即与主导手相同的那一边。
• 第 个人开始行动。两边都有勺子，所以他拿左边的勺子 ，即与主导手相同的那一边。
• 第 个人开始行动。右边没有勺子，但左边还有勺子 ，所以他拿勺子 。每个人都完成了行动并拿了一把勺子。

这种主导手组合满足条件。此外，当第 个人都是左撇子时，也满足条件。

---

输入样例 2

3
1 3 2
R?L

输出样例 2

0

没有满足条件的主导手组合。

---

输入样例 3

12
6 2 9 3 1 4 11 5 12 10 7 8
????????????

输出样例 3

160