200893: [AtCoder]ARC089 F - ColoringBalls

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $1100$ points

Problem Statement

There are $N$ white balls arranged in a row, numbered $1,2,..,N$ from left to right. AtCoDeer the deer is thinking of painting some of these balls red and blue, while leaving some of them white.

You are given a string $s$ of length $K$. AtCoDeer performs the following operation for each $i$ from $1$ through $K$ in order:

  • The $i$-th operation: Choose a contiguous segment of balls (possibly empty), and paint these balls red if the $i$-th character in $s$ is r; paint them blue if the character is b.

Here, if a ball which is already painted is again painted, the color of the ball will be overwritten. However, due to the properties of dyes, it is not possible to paint a white, unpainted ball directly in blue. That is, when the $i$-th character in $s$ is b, the chosen segment must not contain a white ball.

After all the operations, how many different sequences of colors of the balls are possible? Since the count can be large, find it modulo $10^9+7$.

Constraints

  • $1$ $≤$ $N$ $≤$ $70$
  • $1$ $≤$ $K$ $≤$ $70$
  • $|s|$ $=$ $K$
  • $s$ consists of r and b.
  • $N$ and $K$ are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$
$s$

Output

Print the number of the different possible sequences of colors of the balls after all the operations, modulo $10^9+7$.


Sample Input 1

2 2
rb

Sample Output 1

9

There are nine possible sequences of colors of the balls, as follows:

ww, wr, rw, rr, wb, bw, bb, rb, br.

Here, r represents red, b represents blue and wrepresents white.


Sample Input 2

5 2
br

Sample Output 2

16

Since we cannot directly paint white balls in blue, we can only choose an empty segment in the first operation.


Sample Input 3

7 4
rbrb

Sample Output 3

1569

Sample Input 4

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

Sample Output 4

841634130

Input

题意翻译

有 $N$ 个白色的小球排成一排,有一个长为 $K$ 的字符串 $S$。接下来进行 $K$ 次操作。 第 $i$ 个操作,选择一段连续的小球(可以为空),若 $S$ 中第 $i$ 个字符是 `r`,则将这些球染成红色;若是 `b`,则将它们染成蓝色。由于染料的特性,不能直接用蓝色来染白色。 求在进行完所有操作后,所有小球的颜色序列可以有多少种。 对 $10^9+7$ 取模。

加入题单

上一题 下一题 算法标签: