Design A Tree (acm15_design_tree)


Time limit:
1000 ms
Memory limit:
32 MB

You are the best garden designer. You are trying to create a new style of tree. It is called “Left-Right Tree”. These are all details of the style.

  1. Left-Right Tree is a binary tree.
  2. Left-Right Tree has only 1 root node.
  3. Left-Right Tree has exactly N left sticks and M right sticks.

You are trying to draw all possible Left-Right Tree following the details. But it is impossible to do this!, so you want to calculate the number of all possible tree instead.

Count all possible Left-Right Tree following the details and modulo the answer with 9999991.

Input

First line, type T (Number of questions) .

i+1th line, type 2 numbers including N (Number of left sticks) and M (Number of right sticks).

Output

There are T lines.

ith line, display the answer of the ith question.

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None