题目分析 ： （8 4） 可以由（7 4），（6，4），（ 4，4） 基础上转化
意味着一个新加入的元素可以按照它加入的方式分类，从而实现动态规划
核心：加入方式 新加入的元素构成转换环的元素个数（n的约数）
eg: （8，4） 新加入元素自己单独一个环 （7，4）
（6，4）新加入元素自己构成二元环 （6，4）
（4，4）新加入元素自己构成四元环 （4，4）
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+;
const int N=;
LL f[N],inv_f[N];// 阶乘和阶乘的逆元
LL dp[N];
LL p[N]; int cnt;
LL q_pow (LL x,LL k) {// 快速幂求逆元
LL ans=;
while (k) {
if (k&) ans=ans*x%mod;
x=x*x%mod;
k=k>>;
}
return ans;
}
LL c (int n,int m) {// 组合数c(n,m)
if (m>n) return ;
if (m>n-m) m=n-m;
LL x=inv_f[n-m]*inv_f[m]%mod;
return x*f[n]%mod;
}
int n,k;
int main ()
{
f[]=; dp[]=dp[]=;
for (int i=;i<N;i++) f[i]=i*f[i-]%mod;
inv_f[N-]=q_pow (f[N-],mod-);
for (int i=N-;i>=;i--) inv_f[i]=inv_f[i+]*(i+)%mod;
int T; scanf ("%d",&T);
while (T--) {
scanf ("%d %d",&n,&k);
LL sum=; int cnt=;
for (int i=;i<=k;i++)
if (k%i==) {
p[++cnt]=i;// 求得约数
}
for (int i=;i<=n;i++) {
dp[i]=;
for (int j=;j<=cnt;j++) {
if (i-p[j]<) break;
dp[i]=(dp[i]+c(i-,p[j]-)*f[p[j]-]%mod*dp[i-p[j]]%mod)%mod;
// c[i-1][p[j]-1] （选取p[j]-1个元素和新加入的元素构成p[j]元环）
// f[p[j]-1] p[j]个元素构成j元环的个数 （p[j]-1)!
// dp[i-p[j]] 剩余的（ i-p[j])元素的组合个数
}
}
printf("%lld\n",dp[n]);
}
return ;
}