実行時間制限: 4 sec / メモリ制限: 256 MB
配点 : 1100 点
問題文
1,2,..,N の番号のついた N 個の白いボールがこの順に一列に並んでいます。 シカのAtCoDeerくんはこれらのボールに赤と青で色を塗りたいと考えています。 ただし、最終的に白のままのボールがある可能性もあります。
長さ K の文字列 s が与えられます。 AtCoDeerくんは i=1 から i=K まで順に次の操作を行います。
- i 番目の操作: 連続するボールの区間(空でもよい)を一つ選んで、s の i 文字目が
r
なら赤で、b
なら青でそのボール達を塗る
ただし、既に色が塗られているボールに再度色を塗った場合、色は上書きされます。
また、塗料の都合上 まだ色が塗られていない白いボールを直接青で塗ることはできません。
すなわち、s の i 文字目が 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
赤をr
,青をb
,白をw
で表すと、最終的にあり得るボールの列は次の 9 通りです。
ww
, wr
, rw
, rr
, wb
, bw
, bb
, rb
, br
入力例 2
5 2 br
出力例 2
16
白いボールに直接青を塗ることは出来ないので、 1 回目の操作では空の区間を選ぶしかありません。
入力例 3
7 4 rbrb
出力例 3
1569
入力例 4
70 70 bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr
出力例 4
841634130
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