[ARC089F] ColoringBalls
题意翻译
有 $N$ 个白色的小球排成一排，有一个长为 $K$ 的字符串 $S$。接下来进行 $K$ 次操作。
第 $i$ 个操作，选择一段连续的小球（可以为空），若 $S$ 中第 $i$ 个字符是 `r`，则将这些球染成红色；若是 `b`，则将它们染成蓝色。由于染料的特性，不能直接用蓝色来染白色。
求在进行完所有操作后，所有小球的颜色序列可以有多少种。
对 $10^9+7$ 取模。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc089/tasks/arc089_d
$ 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 $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
2 2
rb输出样例 #1
9输入样例 #2
5 2
br输出样例 #2
16输入样例 #3
7 4
rbrb输出样例 #3
1569输入样例 #4
70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr输出样例 #4
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 $ 回目の操作では空の区間を選ぶしかありません。