Link with Bracket Sequence I
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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

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

A bracket sequence is valid if it satisfies any of the following conditions:
  • Its length is 0.
  • It can be represented as (A), where A is a valid bracket sequences.
  • It can be represented as AB, where A and B are both valid bracket sequence.

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

输入描述:

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

The first line contains two integers n,m ().

The second line contains a bracket sequence s of length n.

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

输出描述:

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

Note that the answer maybe 0 due to Link's poor memory.
示例1

输入

复制
3
2 2
()
2 4
)(
2 4
()

输出

复制
1
1
2