我们要求方案数，还是旋转同构的，想burnside，如果我们能计算出转i位不变的满足条件的数量，那么这道题我们就解决了。
考虑转i位时，设tmp=gcd(i,n)，那么就共有tmp个循环节。
当tmp<=k时，只要不是所有的循环节都是女生就可以，所以数量为2^tmp-1，但是要特判k>=n，因为这时所有方案都满足条件。
当tmp>k时，我们需要在提前处理出符合条件的且旋转不变的方案数，考虑dp，我们设f[i][j]表示长度为i的线段第一位是男生，末尾有且仅有j位女生的满足条件的方案，g[i][j]与f相同，只是不限首位。h[i]表示环的，就是线段的去掉首尾相加大与k的，这里注意中间的区间位置不唯一。
最后直接上burnside就好了！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
#define N 2050
#define mod 100000007
using namespace std;
int T,n,m,ans;
int f[N][N],g[N][N],h[N],s[N],pw[N];
int qp(int a,int b){
int c=;
while(b){
if(b&)c=c*a%mod;
a=a*a%mod; b>>=;
}return c;
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
signed main(){
scanf("%lld",&T);
pw[]=;
for(int i=;i<=;i++)pw[i]=(pw[i-]<<)%mod;
while(T--){
ans=;
scanf("%lld%lld",&n,&m);
f[][]=s[]=;f[][]=;
for(int i=;i<=n;i++){
f[i][]=s[i]=s[i-];
for(int j=;j<=m&&j<i;j++){
f[i][j]=f[i-][j-];
(s[i]+=f[i][j])%=mod;
}
}
g[][]=s[]=;
for(int i=;i<=n;i++){
g[i][]=s[i]=s[i-];
for(int j=;j<=m&&j<=i;j++){
g[i][j]=g[i-][j-];
(s[i]+=g[i][j])%=mod;
}
h[i]=s[i];
for(int j=m+;j<=*m&&j<i;j++)
h[i]=(h[i]-(f[i-j][]*max((int),min(j-,m)-max((int),j-m)+(int)))%mod+mod)%mod;
}
for(int i=;i<=n;i++){
int tmp=gcd(i,n);
if(tmp<=m){
if(m>=n)ans=(ans+pw[tmp])%mod;
else ans=(ans+pw[tmp]-+mod)%mod;
}
else ans=(ans+h[tmp])%mod;
}
ans=ans*qp(n,mod-)%mod;
printf("%lld\n",ans);
}
return ;
}