Design a Tree

Time limit3sMemory limit256 MB

Summary

Count binary tree shapes with exactly N left edges and M right edges modulo 9999991 for up to 10000 queries.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

You are a garden designer. You want to grow a new style of tree called the Left-Right Tree. A Left-Right Tree satisfies all of the following.

A Left-Right Tree is a binary tree.
A Left-Right Tree has exactly one root node.
A Left-Right Tree has exactly $N$ left sticks and $M$ right sticks.

A left stick is the edge joining a node to its left child, and a right stick is the edge joining a node to its right child. A Left-Right Tree therefore has $N + M + 1$ nodes. Two Left-Right Trees whose shapes differ count as different trees.

Drawing every Left-Right Tree is impossible because there are too many of them, so count them instead. Print the number of possible Left-Right Trees modulo $9999991$ .

Input

The first line has the number of queries $T$ . ( $1 \le T \le 10000$ )

Each of the next $T$ lines has the number of left sticks $N$ and the number of right sticks $M$ , separated by a space. ( $0 \le N, M \le 125$ )

Output

Print $T$ lines. On line $i$ , print the answer to query $i$ modulo $9999991$ .

Hint

When $N = 1$ and $M = 1$ there are three Left-Right Trees: the root with one left child and one right child, the root with a left child that has a right child, and the root with a right child that has a left child.

The Left-Right Trees for $N = 2$ and $M = 1$ are shown below.

Left-Right Trees for N = 2, M = 1

Examples3

Example 1
Input
```
2
1 1
2 1
```
Expected output
```
3
6
```
Example 2
Input
```
1
0 0
```
Expected output
```
1
```
Example 3
Input
```
3
0 1
1 0
0 5
```
Expected output
```
1
1
1
```