配点 : $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$ $\leq$ $N$ $\leq$ $70$
• $1$ $\leq$ $K$ $\leq$ $70$
• $|s|$ $=$ $K$
• $s$ は r か b のみからなる
• $N,K$ は整数

入力

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

$N$ $K$

$s$

出力

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

2 2
rb

9

赤をr,青をb,白をwで表すと、最終的にあり得るボールの列は次の $9$ 通りです。

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

5 2
br

16

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

7 4
rbrb

1569

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

841634130