Parentheses sequence of length is the sequence containing exactly opening parentheses and exactly closing parentheses
A parentheses sequence is called balanced if one can turn it into a valid math expression by adding characters and . For example, sequences , and are balanced, while , and are not.
A parentheses sequence, of length is called interesting if one can turn it balanced by doing the following operation at most once.
You have to calculate the number of different interesting parentheses sequence of length , and print it modulo .
First line will contain , the number of test cases. Each of the next lines will contain one integer , half the length of the interesting parentheses sequence.
For each testcase, print one line containing an integer , which is the number of different interesting parentheses sequence modulo .
3 1 2 100
2 6 829549001
In the first test case, there are interesting parentheses sequence, these are as follows.
In the second test case, there interesting parentheses sequence, these are as follows.