Person in Charge

• SleepingCup

Problem Description

Little w encountered the following problem in a contest: given a bracket sequence of length $n$ where some positions are fixed and others are undetermined, find the number of valid bracket sequences that can be formed.

As an experienced contestant, Little w solved this problem in an instant. Moreover, he thought it was too trivial for an official contest to include such a simple template problem, so he enhanced the problem and casually threw it to Little c.

Specifically, Little w defines a "super bracket sequence" as a string consisting of the 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 denotes any non-empty string composed of at most $\bm{k}$ characters * (the S in the following two rules has the same meaning);
2. If strings A and B are both valid super bracket sequences, then the strings AB and ASB are also valid super bracket sequences (where AB represents the concatenation of strings A and B);
3. If string A is a valid super bracket sequence, then the strings (A), (SA), and (AS) are also valid super bracket sequences.
4. All valid super bracket sequences can be obtained through the above 3 rules.

For example, when $k = 3$, the string ((**()*(*))*)(***) is a valid super bracket sequence, but the strings *(), (*()*), ((**))*), and (****(*)) are not. In particular, the empty string is not considered a valid super bracket sequence.

Now given a super bracket sequence of length $n$, where some characters are fixed and others are undetermined (denoted by ?), Little w wants to calculate: how many ways are there to replace all undetermined characters with specific characters such that the resulting string is a valid super bracket sequence?

Poor Little c cannot solve this problem, so he has to ask for your 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 result of the answer modulo $10^9 + 7$.

Samples

7 3
(*??*??

5

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

19

Sample 1 Explanation

The following schemes are valid:

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

Sample 3

See bracket/bracket3.in and bracket/bracket3.ans in the contestant's directory.

Sample 4

See bracket/bracket4.in and bracket/bracket4.ans in the contestant's directory.

Data Range

For $100\%$ of the data: $1 \le k \le n \le 500$.