{"problem":{"name":"ColoringBalls","description":{"content":"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 a","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc089_d"},"statements":[{"statement_type":"Markdown","content":"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.\nYou are given a string $s$ of length $K$. AtCoDeer performs the following operation for each $i$ from $1$ through $K$ in order:\n\n*   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`.\n\nHere, 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.\nAfter 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$.\n\n## Constraints\n\n*   $1$ $≤$ $N$ $≤$ $70$\n*   $1$ $≤$ $K$ $≤$ $70$\n*   $|s|$ $=$ $K$\n*   $s$ consists of `r` and `b`.\n*   $N$ and $K$ are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$s$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc089_d","tags":[],"sample_group":[["2 2\nrb","9\n\nThere are nine possible sequences of colors of the balls, as follows:\n`ww`, `wr`, `rw`, `rr`, `wb`, `bw`, `bb`, `rb`, `br`.\nHere, `r` represents red, `b` represents blue and `w`represents white."],["5 2\nbr","16\n\nSince we cannot directly paint white balls in blue, we can only choose an empty segment in the first operation."],["7 4\nrbrb","1569"],["70 70\nbbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr","841634130"]],"created_at":"2026-03-03 11:01:13"}}