Design a Tree

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.

1. A Left-Right Tree is a binary tree.
2. A Left-Right Tree has exactly one root node.
3. 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$.

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$)

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

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.