AT_arc089_d [ARC089F] ColoringBalls

[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/A

N/A

### 制約 - $ 1 $ $