时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
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.