题目描述

有 $N$ 个编号为 $1,2,...,N$ 的白球按顺序排成一行。AtCoDeer 君想用红色和蓝色给这些球染色。最终，可能还会有部分球保持白色。

给定一个长度为 $K$ 的字符串 $s$。AtCoDeer 君将对 $i=1$ 到 $i=K$ 依次进行如下操作：

• 第 $i$ 次操作：选择一段连续的球区间（可以为空），如果 $s$ 的第 $i$ 个字符为 r，则用红色染色；如果为 b，则用蓝色染色。

注意，如果对已染色的球再次染色，则会覆盖原有的颜色。另外，由于染料的限制，尚未被染色的白球不能直接用蓝色染色。即，当 $s$ 的第 $i$ 个字符为 b 时，不能选择包含白球的区间。

所有操作结束后，问可能得到多少种不同的球颜色排列。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$ $s$

输出格式

请输出所有操作结束后可能得到的球颜色排列数量，对 $10^9+7$ 取模。

样例 1

输入

2 2
rb

输出

9

样例 2

输入

5 2
br

输出

16

样例 3

输入

7 4
rbrb

输出

1569

样例 4

输入

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

输出

841634130

说明/提示

限制条件

• $1 \leq N \leq 70$
• $1 \leq K \leq 70$
• $|s| = K$
• $s$ 仅由 r 和 b 组成
• $N,K$ 均为整数

样例解释 1

若用 r 表示红色，b 表示蓝色，w 表示白色，则最终可能出现的球颜色排列有以下 $9$ 种：ww, wr, rw, rr, wb, bw, bb, rb, br

样例解释 2

由于不能直接将白球染成蓝色，所以第一次操作只能选择空区间。

由 ChatGPT 5 翻译