We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Combinatorics
  4. Div and Span

Div and Span

Maya is teaching Alex about HyperText Markup Language (HTML). Alex is confused about div and span tags, so Maya decides to reduce the concept to a simpler visual by representing div tags as square brackets and span tags as parentheses. In other words, she represents <div> as [, </div> as ], <span> as (, and </span> as ).

We use the following rules to determine the validity of a configuration:

  1. The empty string (""), a single pair of square brackets [], and single pair of parentheses () are all considered to be valid configurations. We can express each of these as .
  2. A valid configuration, , which does not contain square brackets is called a normal configuration, which we can express as . For example, () is normal.
  3. Two or more consecutive valid configurations (e.g., ) also constitute a valid configuration. For example, [][], ()(), and []()[] are all valid.
  4. The following configurations are also valid: [V], (N).
    For example, [[(())]()], ((())), and [(())[]] are all valid; however, ([]) is not valid (you cannot nest a div tag inside a span tag).

Given some number of distinguishable square brackets, , and some number of distinguishable parentheses, , how many valid configurations can we build using the above rules? As this answer can be very large, print it modulo .

Input Format

The first line contains a single positive integer, , denoting the number of test cases.
Each of the subsequent lines contains positive space-separated integers describing the respective values of (the number of distinguishable square brackets) and (the number of distinguishable parentheses).

Constraints

Output Format

For each test case, print the number of different valid configurations modulo .

Sample Input

3
1 1
1 2
2 2

Sample Output

3
18
160

Explanation

For the first test case, , , these are valid configurations:

  1. []()
  2. ()[]
  3. [()]

Thus, we print the result of on the first line.

For the second test case, if brackets and parentheses were not distinguishable, we would have only different configurations:

[()]() []()() [](())
()[]() [()()] [(())]
()()[] ()[()] (())[]

However, they are distinguishable, so [](1)(2) is not same as [](2)(1) (where (1) and (2) are the respective first and second pairs of parentheses. For this reason, we have possible configurations and print the result of on a new line.