题目描述

$1,2,..,N$ の番号のついた $N$ 個の白いボールがこの順に一列に並んでいます。 シカのAtCoDeerくんはこれらのボールに赤と青で色を塗りたいと考えています。 ただし、最終的に白のままのボールがある可能性もあります。

長さ $K$ の文字列 $s$ が与えられます。 AtCoDeerくんは $i=1$ から $i=K$ まで順に次の操作を行います。

• $i$ 番目の操作: 連続するボールの区間(空でもよい)を一つ選んで、$s$ の $i$ 文字目が r なら赤で、 b なら青でそのボール達を塗る

ただし、既に色が塗られているボールに再度色を塗った場合、色は上書きされます。 また、塗料の都合上 まだ色が塗られていない白いボールを直接青で塗ることはできません。 すなわち、$s$ の $i$ 文字目が b のとき、白いボールを含む区間を選ぶことはできません。

すべての操作が終わったあとにありうるボールの色の列が何通りありうるか求めてください。 答えは大きくなる可能性があるので、 $10^9+7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $s$

输出格式

すべての操作が終わったあとにありうるボールの色の列が何通りあるかを $10^9+7$ で割ったあまりを出力せよ。

题目大意

有 $N$ 个白色的小球排成一排，有一个长为 $K$ 的字符串 $S$。接下来进行 $K$ 次操作。

第 $i$ 个操作，选择一段连续的小球（可以为空），若 $S$ 中第 $i$ 个字符是 r，则将这些球染成红色；若是 b，则将它们染成蓝色。由于染料的特性，不能直接用蓝色来染白色。

求在进行完所有操作后，所有小球的颜色序列可以有多少种。

对 $10^9+7$ 取模。

2 2
rb

9

5 2
br

16

7 4
rbrb

1569

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

841634130

提示

制約

• $1$ $<\ =$ $N$ $<\ =$ $70$
• $1$ $<\ =$ $K$ $<\ =$ $70$
• $|s|$ $=$ $K$
• $s$ は r か b のみからなる
• $N,K$ は整数

Sample Explanation 1

赤をr,青をb,白をwで表すと、最終的にあり得るボールの列は次の $9$ 通りです。 ww, wr, rw, rr, wb, bw, bb, rb, br

Sample Explanation 2

白いボールに直接青を塗ることは出来ないので、 $1$ 回目の操作では空の区間を選ぶしかありません。