← 返回题目列表

AtCoder · arc089_d

F. 着色球

中文机器翻译题面 查看原题

分数: 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