2017 Atlantic Canadian Preliminary Contest

Start

2017-10-13 15:30 UTC

2017 Atlantic Canadian Preliminary Contest

End

2017-10-13 20:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -559 days 0:13:23

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
AVL++

/problems/atlantic-canada17.avlplusplus/file/statement/en/img-0001.jpg
Image by Ilya Klukhov (Shutterstock), Used under license

An AVL tree, named after its inventors, Adelson-Velskii and Landis, is a binary search tree with an additional constraint that keeps the tree balanced. The balance factor of a node $x$, denoted $\mathit{bf}(x)$, is defined to be $H(x_ R) - H(x_ L)$, where $H(\, )$ denotes height, $x_ R$ is the right subtree of $x$, and $x_ L$ is the left subtree of $x$. (The height of a tree is the number of edges in the longest simple path from the root to any leaf. It follows that the height of a tree containing a single node is $0$. The height of the empty tree, i.e., the tree with no nodes, is typically defined to be $-1$.) In an AVL tree, the only balance factors permitted are $\{ -1,0,1\} $, i.e., $|\mathit{bf}(x)| \leq 1$ for every node $x$.

Two AVL trees $T_1$ and $T_2$ are isomorphic if there is a bijection $f : X_1 \rightarrow X_2$, where $X_1$ is the set of nodes in $T_1$, and $X_2$ is the set of nodes in $T_2$, such that for all $x,y \in X_1$, $y$ is the right (respectively, left) child of $x$ in $T_1$ if and only if $f(y)$ is the right (respectively, left) child of $f(x)$ in $T_2$. In other words, two AVL trees are isomorphic if they have the same “shape” (we are not concerned with the values stored in the nodes).

Now consider one way to generalize the AVL constraint. Let $m \geq 0$ be an integer, and define an AVL-$m$ tree to be a binary search tree satisfying $|\mathit{bf}(x)| \leq m$ for every node $x$. This gives rise to an interesting question: How many differently shaped (non-isomorphic) AVL-$m$ trees are there with a given height $h$? The figure below illustrates the answer when $m=2$ and $h=2$.

\includegraphics[width=0.75\textwidth ]{trees.png}
Figure 1: There are $21$ AVL-$2$ trees with height $2$

Input

The first line of input contains an integer $Q$ $(1 \leq Q \leq 100)$ indicating the number of queries to follow. Each of the next $Q$ lines contains a query consisting of two space-separated integers $m$ and $h$ $(0 \leq m \leq 100, 0 \leq h \leq 1000)$.

Output

For each query, output a line containing the number of non-isomorphic AVL-$m$ trees with height $h$. Since these numbers may be large, report each answer mod $(10^9+7)$.

Sample Input 1 Sample Output 1
4
1 1
2 1
0 2
2 2
3
3
1
21