Little w encountered a problem during a competition: given a bracket sequence of length $n$ where some positions are already determined and others are not, find the total number of such valid bracket sequences.

Little w, being a veteran, solved this problem at a glance. Furthermore, he felt that such a simple template problem in an official competition was too trivial, so he strengthened the problem and passed 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 valid super bracket sequences, where $S$ denotes any non-empty string consisting of no more than $k$ * characters (this definition of $S$ applies to the following two rules as well).
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$ denotes the concatenation of string $A$ and string $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 3 rules above.

For example, if $k = 3$, then the string ((**()*(*))*)(***) is a valid super bracket sequence, but the strings *(), (*()*), ((**))*), and (****(*)) are not. Specifically, an empty string is not considered a valid super bracket sequence.

Now, given a super bracket sequence of length $n$, where some positions are already determined and others are not (represented by ?), little w wants to calculate: how many ways are there to determine all the undetermined characters such that the resulting string is a valid super bracket sequence?

Poor little c does not know how to solve this problem, so he asks for your help.

Input

Read the data from the file bracket.in.

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

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

Output

Output to the file bracket.out.

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

Examples

Input 1

7 3
(*??*??

Output 1

5

Note 1

The following schemes are valid:

1. (**)*()
2. (**(*))
3. (*(**))
4. (*)**()
5. (*)(**)

Input 2

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

Output 2

19

Examples 3

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

Examples 4

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

Constraints

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