ColoringBalls

AtCoder

IDarc089_d

Time4000ms

Memory256MB

Difficulty—

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 are given a string $s$ of length $K$. AtCoDeer performs the following operation for each $i$ from $1$ through $K$ in order: * 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`. Here, 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. After 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$. ## Constraints * $1$ $≤$ $N$ $≤$ $70$ * $1$ $≤$ $K$ $≤$ $70$ * $|s|$ $=$ $K$ * $s$ consists of `r` and `b`. * $N$ and $K$ are integers. ## Input Input is given from Standard Input in the following format: $N$ $K$ $s$ [samples]

Samples

Input #1

2 2
rb

Output #1

9

There are nine possible sequences of colors of the balls, as follows:
`ww`, `wr`, `rw`, `rr`, `wb`, `bw`, `bb`, `rb`, `br`.
Here, `r` represents red, `b` represents blue and `w`represents white.

Input #2

5 2
br

Output #2

16

Since we cannot directly paint white balls in blue, we can only choose an empty segment in the first operation.

Input #3

7 4
rbrb

Output #3

Input #4

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

Output #4

841634130

API Response (JSON)

{
  "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 a...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments