Problem A
AVL++

Image by Ilya Glukhov (iStock), Used under license

An AVL tree, named after its two 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(\, )$ is height, $x_ R$ is the right subtree of $x$, and $x_ L$ is the left subtree of $x$. (The height of a (sub)tree is the number of edges in the longest simple path from its root to any of its leaves. 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 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 any 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$.

Figure 1: There are $21$ AVL-$2$ trees with height $2$

Input

The first line of input contains an integer, $T$ $(1 \leq T \leq 100)$, the number of test cases. Each of the next $T$ lines contains a single test case consisting of two space-separated integers, $m$ and $h$, with $0 \leq m \leq 100$ and $0 \leq h \leq 1\, 000$.

Output

For each test case, 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)$.

4
1 1
2 1
0 2
2 2

3
3
1
21