题目描述

一个长度为 $n$ 的序列 $a_0\sim a_{n-1}$，第 $0$ 秒时 $a_i=i$。

第 $1$ 秒及之后的每一秒，序列上的数会同时进行移动。具体的，$a_x$ 变为 $b_{a_x}$。其中 $b$ 是一个 $0\sim n-1$ 的排列。

每一秒移动后，小 X 会将数进行分类，他会从以下分类标准中选择一个：

1. 若 $a_i\equiv a_j \pmod m$ 且 $i\equiv j\pmod m$，则 $a_i$ 和 $a_j$ 同组。
2. 若 $\lfloor\frac{a_i}{m}\rfloor=\lfloor\frac{a_j}{m}\rfloor$ 且 $\lfloor\frac{i}{m}\rfloor=\lfloor\frac{j}{m}\rfloor$，则 $a_i$ 和 $a_j$ 同组。

求出有多少个 $0\sim n-1$ 的排列 $b$，使得无论小 X 每秒选择哪个分类标准，都满足条件：

• 若 $t_1\ge 1$ 与 $t_2\ge 1$ 秒时采取相同的分类标准，则任意 $a_i$ 所在组的大小在 $t_1$ 与 $t_2$ 秒时相等。

答案对 $10^9+7$ 取模。

输入格式

共 $T$ 组数据，第一行输入 $T$。

每组数据一行，输入 $n,m$。

输出格式

共 $T$ 行，每行一个整数代表排列 $b$ 的数量，答案对 $10^9+7$ 取模。

5
5 3
4 2
8 2
10 4
192 321

2
4
48
8
389110882

提示

样例解释

对于第二组数据，满足条件的 $b$ 有：

$\{0,1,2,3\},\{1,0,3,2\},\{2,3,0,1\},\{3,2,1,0\}$。

当 $b=\{1,0,3,2\}$ 时：

• $t=1$ 秒时，$a=\{1,0,3,2\}$。

若选择第一种分类标准，则 $a_0,a_1,a_2,a_3$ 所在组大小均为 $2$。（$a_0$ 与 $a_2$ 一组，$a_1$ 与 $a_3$ 一组。）

若选择第二种分类标准，则 $a_0,a_1,a_2,a_3$ 所在组大小均为 $2$。（$a_0$ 与 $a_1$ 一组，$a_2$ 与 $a_3$ 一组。）

• $t=2$ 秒时，$a=\{0,1,2,3\}$。

若选择第一种分类标准，则 $a_0,a_1,a_2,a_3$ 所在组大小均为 $2$。

若选择第二种分类标准，则 $a_0,a_1,a_2,a_3$ 所在组大小均为 $2$。

• $t=3$ 秒时，与 $t=1$ 秒相同。

• $t=4$ 秒时，与 $t=2$ 秒相同。

• $\dots$

所以 $b=\{1,0,3,2\}$ 时满足条件。

数据范围

本题采用捆绑测试。

• Subtask 1（10 pts）：$T,n,m \le 8$。
• Subtask 2（15 pts）：$n\le m$。
• Subtask 3（15 pts）：$m \mid n$。
• Subtask 4（60 pts）：无特殊限制。

对于所有数据，$1 \le T,n,m\le 5\times 10^5$。