Link has a bracket sequence of length , which is a subsequence of a valid bracket sequence of length .

Link doesn't remember , so he wonders the number of possible sequences .

A bracket sequence is valid if it satisfies any of the following conditions:

• Its length is .

• It can be represented as , where is a valid bracket sequences.

• It can be represented as , where and are both valid bracket sequence.

A sequence is a subsequence of a sequence if can be obtained from by deletion of several (possibly, zero or all) elements.

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases  (). Description of the test cases follows.

The first line contains two integers  ().

The second line contains a bracket sequence  of length .

It is guaranteed that the sum of  over all test cases does not exceed .

输出描述:

For each test cases, output the number of possible sequences  modulo .

Note that the answer maybe  due to Link's poor memory.

3
2 2
()
2 4
)(
2 4
()

1
1
2