P7914 [CSP-S 2021] Bracket Sequence

Little w encountered such a problem in a contest: given a valid bracket sequence of length $n$, where some positions are already fixed and some are not, find how many such bracket sequences there are. The battle-hardened little w solved it instantly. Not only that, he also felt that using such a simple template problem in an official contest was too easy, so he strengthened the problem and casually threw it to little c. Specifically, little w defines a “super bracket sequence” as a string consisting of characters `(`, `)`, and `*`. For a given constant $k$, the definition of a “valid super bracket sequence” is as follows: 1. `()` and `(S)` are both valid super bracket sequences, where `S` is any non-empty string consisting only of **no more than** $\bm{k}$ **characters** `*` (the `S` in the next two rules has the same meaning). 2. If both strings `A` and `B` are valid super bracket sequences, then `AB` and `ASB` are also valid super bracket sequences, where `AB` means concatenating string `A` and string `B`. 3. If string `A` is a valid super bracket sequence, then `(A)`, `(SA)`, and `(AS)` are also valid super bracket sequences. 4. All valid super bracket sequences can be obtained using the above 3 rules. For example, if $k = 3$, then the string `((**()*(*))*)(***)` is a valid super bracket sequence, but `*()`, `(*()*)`, `((**))*)`, and `(****(*))` are not. In particular, the empty string is also not considered a valid super bracket sequence. Now you are given a super bracket sequence of length $n$, where some positions have already been fixed, and the other positions are not fixed (denoted by `?`). Little w wants to compute: in how many ways can we determine all the unknown characters one by one so that the resulting string is a valid super bracket sequence? Poor little c cannot solve this problem, so he has to ask you for help.

The first line contains two positive integers $n, k$. The second line contains a string $S$ of length $n$, consisting only of `(`, `)`, `*`, and `?`.

Output a non-negative integer, representing the answer modulo ${10}^9 + 7$.

**[Sample Explanation #1]** The following solutions are valid: ```plain (**)*() (**(*)) (*(**)) (*)**() (*)(**) ``` **[Constraints]** | Test Point ID | $n \le$ | Special Property | |:-:|:-:|:-:| | $1 \sim 3$ | $15$ | None | | $4 \sim 8$ | $40$ | None | | $9 \sim 13$ | $100$ | None | | $14 \sim 15$ | $500$ | The string $S$ contains only the character `?` | | $16 \sim 20$ | $500$ | None | For $100\%$ of the testdata, $1 \le k \le n \le 500$. Translated by ChatGPT 5