F - ColoringBalls Editorial /

Time Limit: 4 sec / Memory Limit: 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 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