人工神经网络可以建模为有向无环图。图中的边代表人工神经信号束，其中神经信号束可以用数学上的张量（或非正式地称为多维数组）来表示。图中的节点代表神经信号束的处理操作。

在本题中，神经网络仅处理二维张量（即矩阵）形式的神经信号束，且仅包含三种类型的处理操作：输入操作、乘法操作和卷积操作。我们将详细解释它们。一个处理操作消耗一个或两个信号束，并生成一个信号束。在我们的问题中，整个神经网络包含一个或多个输入操作，且只允许存在一个输出信号束（即未被任何操作处理的神经信号）。

输入操作从神经网络的实际输入流（即张量序列）中生成一个张量。实际输入数据不作为图中的边建模；相反，输入操作节点入度为零，并有一条出边，用于将输入信号束建模或复制为一个张量。输入操作将从输入流中逐个产生张量。

乘法操作以两个张量作为输入，然后将这两个张量相乘并生成一个乘积张量。在我们的问题中，所有张量都是矩阵，因此两个输入矩阵的尺寸必须满足矩阵乘法的合法性。注意，输入的顺序很重要，除非两个输入张量实际上是同一个；换句话说，如果 $A$ 和 $B$ 不相同，则 $A$ 乘以 $B$ 与 $B$ 乘以 $A$ 通常是不同的。

卷积操作以一个张量作为输入，并包含一些属性，如核大小和步长。为了简化问题，这里我们仅允许使用 $2 \times 2$ 核大小、步长为 $2$ 且无填充（不在外部添加 $0$）的卷积操作。我们关注的是张量形状：如果输入张量的形状为 $(x, y)$（第一维大小为 $x$，第二维大小为 $y$），则其输出张量的形状为 $(\lfloor \frac{x}{2} \rfloor, \lfloor \frac{y}{2} \rfloor)$。注意，我们不允许张量具有空尺寸，因此输出张量的每个维度都应大于 $0$。

此外，在本题中，我们不允许神经网络包含重复节点。仅当两个节点的输入实际上是相同的节点时，才称这两个节点是重复的。例如，左侧的神经网络包含重复节点（红框中的节点）。注意，如右侧神经网络的另一个例子所示，蓝框中的节点和紫框中的节点是不同的，因为它们的输入节点不同。

输入形状：$3 \times 5$；$2 \times 2$ 核，步长 $= 2$；输出形状：$1 \times 2$

我们将神经网络的输入格式称为其输入张量的形状。例如，如果一个神经网络有两个输入张量，第一个张量的形状为 $(x_1, y_1)$，第二个张量的形状为 $(x_2, y_2)$，则我们将该神经网络的输入格式称为 $(x_1, y_1), (x_2, y_2)$。如果两个神经网络的输入格式不同或它们的图模型不同，则称它们是不同的。

对于给定的 $N$ 和 $D$，假设张量维度大小的上限为 $2^D-1$，我们想知道具有 $N$ 个节点的不同神经网络的数量。由于该数字可能很大，请输出其除以 $1000000007$ 的余数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例包含一行，包含两个整数 $N$ 和 $D$ ($N \le 7$ 且 $D \le 50$)。

输出格式

对于每个测试用例，打印一行作为其对应的答案。

样例

输入 1

3
2 2
3 3
4 3

输出 1

7
749
2391

说明

对于第一个测试用例，它包含以下不同的神经网络：一个输入节点连接到一个输入张量形状为 $1 \times 1$、$2 \times 2$ 或 $3 \times 3$ 的乘法节点；一个输入节点连接到一个输入张量形状为 $2 \times 2$、$2 \times 3$、$3 \times 2$ 或 $3 \times 3$ 的卷积节点。

对于第二个测试用例，它包含以下不同的神经网络，每个网络下方的数字表示该图上的输入格式数量。