分数: 1100 点
问题陈述
有 N 白球排成一排,编号 1,2,..,N 从左到右。 在CoDeer,鹿正在考虑将其中一些球涂成红色和蓝色,同时将其中一些留为白色。
给你一个字符串 s 长度 K。 AtCoDeer 对每个执行以下操作 i 来自 1 通过 K 按顺序:
- 的 i-th 操作:选择一个连续的球段(可能为空),并将这些球涂成红色,如果 i- 第一个字符 s is
r;如果角色是,则将它们涂成蓝色b.
这里,如果已经绘制的球再次绘制,则球的颜色将被覆盖。
但由于染料的特性, 无法直接将未涂漆的白色球涂成蓝色。
也就是说,当 i- 第一个字符 s is 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