题目描述

莫阿娜与毛伊一起开始了新的航行。但这一次，她再次遭遇了猛烈的风暴——为了防止小船沉没，她需要正确地固定船帆。

船帆由 $n$ 个绳结固定，每个绳结可以处于以下三种状态之一：

• wet——在水中，未固定到桅杆上；
• ready——系在桅杆上，准备使用；
• bound——紧密系牢并固定，以防被强风吹走。

目前所有绳结都处于“w”状态。在一个操作中，莫阿娜可以选择一段连续编号的绳结，并执行以下之一：

• 将它们全部转换为“r”状态；
• 如果其中没有任何一个绳结处于“w”状态，则将它们全部转换为“b”状态。

给定莫阿娜需要执行的一系列 $q$ 个操作，但每个操作仅知道需要将某个连续段的绳结转换为哪种状态（即整个操作序列由字母“r”和“b”组成的字符串给出）。

请确定执行完整操作序列后，可能的绳结配置数量。如果存在至少一个绳结在两种配置中处于不同状态，则称这两种配置不同。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 和 $q$——分别表示绳结的数量和操作的数量（$1 \le n, q \le 70$）。

接下来是一个由 $q$ 个字符组成的字符串，每个字符为“r”或“b”，表示将某段连续绳结转换为相应状态的操作。

输出格式

输出一个整数——执行完整操作序列后不同的绳结配置数量，对 $10^9 + 7$ 取模后的结果。

2 1
r

4

3 2
rb

22

6 4
rbrb

627

提示

在第一个样例中，唯一操作可以选择四个段中的任意一个：空段、$[1]$、$[2]$、$[1, 2]$。

在第二个样例中，可能的船帆配置包括：全部为白色、任意一段为红色（$6$ 种情况）、任意一段为蓝色（另外 $6$ 种情况）、一段红色与一段蓝色相邻（$4$ 种情况），以及另外 $5$ 种情况（如果第一次操作选择段 $[1, 2, 3]$，第二次操作选择任意长度为 $1$ 或 $2$ 的蓝色段）。

---

翻译由 DeepSeek V3 完成