题目描述

有 $N$ 个白色的球排成一行，从左到右编号为 $1,2,..,N$。AtCoDeer 驯鹿想要把其中一些球涂成红色和蓝色，同时保留一些白色的球。

给定长度为 $K$ 的字符串 $s$。AtCoDeer 按顺序执行以下操作，对每个 $i$ 从 $1$ 到 $K$：

• 第 $i$ 步操作：选择一段连续的球（可以为空），如果 $s$ 的第 $i$ 个字符是 r，则将这些球涂成红色；如果字符是 b，则将这些球涂成蓝色。

这里，如果一个已经涂过颜色的球再次被涂色，球的颜色将被覆盖。然而，由于染料的特性，不能直接将一个白色、未涂色的球涂成蓝色。也就是说，当 $s$ 的第 $i$ 个字符是 b 时，选择的连续球段不能包含白色的球。

完成所有操作后，有多少种可能的球颜色序列？由于数量可能很大，将结果对 $10^9+7$ 取模。

约束条件

• $1$ $≤$ $N$ $≤$ $70$
• $1$ $≤$ $K$ $≤$ $70$
• $|s|$ \= $K$
• $s$ 由字符 r 和 b 构成。
• $N$ 和 $K$ 是整数。

---

输入

输入数据从标准输入读取。数据格式如下：

$N$ $K$ $s$

输出

输出完成所有操作后，不同的球颜色序列的数量，对 $10^9+7$ 取模。

---

示例输入 1

2 2
rb

示例输出 1

9

有九种可能的球颜色序列，如下所示：

ww, wr, rw, rr, wb, bw, bb, rb, br。

这里，r 表示红色，b 表示蓝色，w 表示白色。

---

示例输入 2

5 2
br

示例输出 2

16

由于不能直接将白色的球涂成蓝色，在第一步操作中只能选择一个空段。

---

示例输入 3

7 4
rbrb

示例输出 3

1569

---

示例输入 4

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

示例输出 4

841634130