Problem Description

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.

Input Format

The first line contains two positive integers $n, k$.

The second line contains a string $S$ of length $n$, consisting only of (, ), *, and ?.

Output Format

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

7 3
(*??*??

5

10 2
???(*??(?)

19

见附件中的 bracket/bracket3.in

见附件中的 bracket/bracket3.ans

见附件中的 bracket/bracket4.in

见附件中的 bracket/bracket4.ans

Hint

[Sample Explanation #1]

The following solutions are valid:

(**)*()
(**(*))
(*(**))
(*)**()
(*)(**)

[Constraints]

For $100\%$ of the testdata, $1 \le k \le n \le 500$.

Translated by ChatGPT 5