{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $1$ $≤$ $N$ $≤$ $70$\n*   $1$ $≤$ $K$ $≤$ $70$\n*   $|s|$ $=$ $K$\n*   $s$ consists of `r` and `b`.\n*   $N$ and $K$ are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$s$"},{"iden":"sample input 1","content":"2 2\nrb"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"5 2\nbr"},{"iden":"sample output 2","content":"16\n\nSince we cannot directly paint white balls in blue, we can only choose an empty segment in the first operation."},{"iden":"sample input 3","content":"7 4\nrbrb"},{"iden":"sample output 3","content":"1569"},{"iden":"sample input 4","content":"70 70\nbbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr"},{"iden":"sample output 4","content":"841634130"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}