每年圣诞节，算法爱好者社区的成员们都会互赠礼物。这个传统存在一些问题，容易引发矛盾，因为总有一些成员收到的礼物比别人多。今年，社区决定引入一种协调且公平的系统，即“秘密圣诞老人”（Secret Santa）。

“秘密圣诞老人”的理念非常简单：社区中的每位成员都被分配给一个人，并向其发送一份礼物。这样，每位成员准备一份礼物，同时也收到一份礼物。成员也有可能被分配给自己，这种情况下他们只需给自己送一份礼物。

社区成员对这个想法非常热衷，现在他们想要确定谁该给谁送礼物。然而，他们需要考虑到邮政系统的运作方式——包裹能否从一个城镇投递到另一个城镇，取决于当天的风力大小。

社区共有 $n$ 名成员。每位成员居住在不同的城镇，城镇编号从 $1$ 到 $n$。如果风速为 $a$，那么包裹可以从城镇 $k$ 投递到城镇 $l$，当且仅当 $k - n + a < l < k + a$。

你的任务是计算在给定当天风速的情况下，有多少种分配方式，使得所有成员都能在同一天送出礼物。由于结果可能非常大，你只需要求出结果对 $10^9 + 7$ 取模后的值。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 10$)。接下来是各测试用例的描述。

每个测试用例由单行组成，包含两个整数 $n$ 和 $a$ ($1 \le a \le 200, 1 \le n \le 10^6, a < n$)，分别代表社区成员的数量和风速。

输出格式

对于每个测试用例，输出一个整数：社区成员之间分配礼物的方案数，对 $10^9 + 7$ 取模。

样例

输入 1

3
4 2
5 2
16 5

输出 1

5
13
418144253