200893: [AtCoder]ARC089 F - ColoringBalls
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 isb
.
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
andb
. - $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 w
represents 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