Counting Super Parentheses Sequences

A super parentheses sequence is a string consisting of the characters (, ), and * defined with respect to an integer constant \(k\) according to the following rules:

• The strings () and (S) are valid, where \(S\) is a non‐empty string consisting solely of at most \(k\) asterisks (*).
• If A and B are valid sequences then AB (concatenation) and A S B are valid, where \(S\) is again any non‐empty string of at most \(k\) asterisks.
• If A is a valid sequence then (A), (S A) and (A S) are also valid.
• All valid super parentheses sequences can be generated by the above three rules. Note that the empty string is not valid.

We are given a string of length \(n\) representing a super parentheses sequence. Some positions already have a fixed character (one of (, ), or *) while other positions are unspecified and denoted by ?. Your task is to count the number of ways to replace every ? with one of the allowed characters so that the final string is a valid super parentheses sequence.

Additional constraints:

• The first character must be ( and the last character must be ).
• Any maximal consecutive block of asterisks must have length at most \(k\).
• The sequence must be balanced in the usual sense (every ( is eventually matched by a ) in the proper order).

inputFormat

The first line contains two integers \(n\) and \(k\) \( (2 \le n \le 500,\; 1 \le k \le n)\) — the length of the string and the maximum allowed number of consecutive asterisks.

The second line contains a string of length \(n\) consisting of characters (, ), * and ?.

outputFormat

Output a single integer — the number of ways to replace all ? characters so that the final string is a valid super parentheses sequence. It is guaranteed that the answer fits in the range of a 64-bit signed integer.

sample

6 1
(()())

1