좌우 트리 설계

당신은 정원 디자이너다. 좌우 트리라고 부르는 새로운 양식의 나무를 만들려고 한다. 좌우 트리는 다음 조건을 모두 만족한다.

1. 좌우 트리는 이진 트리다.
2. 좌우 트리의 루트 노드는 하나다.
3. 좌우 트리에는 왼쪽 가지가 정확히 $N$개, 오른쪽 가지가 정확히 $M$개 있다.

왼쪽 가지는 어떤 노드와 그 노드의 왼쪽 자식을 잇는 간선이고, 오른쪽 가지는 어떤 노드와 그 노드의 오른쪽 자식을 잇는 간선이다. 그래서 좌우 트리의 노드 수는 항상 $N + M + 1$이다. 모양이 다른 두 좌우 트리는 서로 다른 것으로 센다.

조건을 만족하는 좌우 트리를 전부 그려 보려고 했지만 수가 너무 많아 그릴 수 없다. 대신 개수를 세기로 했다. 가능한 좌우 트리의 개수를 $9999991$로 나눈 나머지를 구하라.

첫째 줄에 질의의 개수 $T$가 주어진다. ($1 \le T \le 10000$)

다음 $T$개의 줄에 각각 왼쪽 가지의 개수 $N$과 오른쪽 가지의 개수 $M$이 공백을 사이에 두고 주어진다. ($0 \le N, M \le 125$)

$T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 $9999991$로 나눈 나머지를 출력한다.

$N = 1$, $M = 1$이면 좌우 트리는 세 개다. 루트에 왼쪽 자식과 오른쪽 자식이 하나씩 달린 모양, 루트의 왼쪽 자식에 오른쪽 자식이 달린 모양, 루트의 오른쪽 자식에 왼쪽 자식이 달린 모양이다.

$N = 2$, $M = 1$인 좌우 트리는 다음 그림과 같다.