AT_arc089_d [ARC089F] ColoringBalls

有 $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 \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 翻译