Migrated from Lutece 2661 红蓝之争

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

坤坤有 $N$ 个白球排成一排，从左至右依次标号为 $1,2,\ldots,N$。无聊的他今天想将一部分球染成红色或蓝色。

给定一个长度为 $K$ 的字符串 $s$，坤坤将根据这些字符依次进行 $K$ 次操作：

• 对于第 $i$ 次操作：选择一连串球（串长可以为 $0$），如果第 $i$ 个字符是 r，则将所选的球染成红色；如果第 $i$ 个字符是 b，则将所选的球染成蓝色。

球的染色是可以覆盖的，例如蓝球染红色就变成红球。

但坤坤不希望这个游戏这么简单，于是要求不能直接将白球染成蓝色，即当染蓝色的时候，所选的球不能含有白球。

那么当坤坤做完所有操作后，一共有多少种染色结果呢？

由于可能的结果数会很大，所以请将结果模 $10^9+7$ 后再输出。

Input

第一行输入为用一个空格间隔的整数 $N$ 和 $K$，其中 $1\leq N,K \leq 70$。

第二行输入为一个长度为 $K$ 的字符串 $s$，其中只含有 r 和 b 两种字母。

Output

输出一个整数，表示可能染色结果总数对 $10^9+7$ 取模后的结果

Samples

2 2
rb

9

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

841634130

Resources

2021 UESTC ICPC Training for String and Search Algorithm