题意：

总共有N本书，要放到一个K层的书架上去。假设每一层最后放了$cnt_i$本书，f[i]为斐波那契数列(f[0]=0,f[1]=1)，定义第i层书架的稳定值为$stable_i=f[cnt_i]$，第i层书架的美观值为$beauty_i=2^{stable_i}-1$，定义分数为$score=gcd(beauty_1,beauty_2,...,beauty_k)$。问分数的期望为多少。

思路：

有两个公式，

$gcd(a^m-1,b^n-1)=a^{gcd(m,n)}-1$，其中a,m,n>0。

$gcd(f[x],f[y])=f_{gcd(m,n)}$。

假设每一层放了$x_1,x_2,...,x_k$本书，即$x_1+x_2+...+x_k=n$，则分数为$gcd(2^{f[x_1]}-1,2^{f[x_2]}-1,...,2^{f[x_k]}-1)$，由第一个公式，有$2^{gcd(f[x_1],f[x_2],...,f[x_k])}-1$。由第二个公式，继续化为$2^{f_{gcd(x_1,x_2,...,x_k)}}-1$。

设$g=gcd(x_1,x_2,...,x_k)$，则有$x_1=s_1*g,x_2=s_2*g,...,x_k=s_k*g(s为系数)$，相加有$n=g*(s_1+s_2+...+s_k)$，所以g可以由枚举n的因子得到。

对于每个g，问题就转化为了将$\frac{n}{g}$个系数分配给k层的问题，这是可以有空位的整数拆分问题，方案数为$C_{\frac{n}{g}+k-1}^{k-1}$（具体可见https://wenku.baidu.com/view/6f822211dd36a32d7375816b.html）。

然而这样子是有重复的，比如n=15，k=1，那么g有1,3,5,15，如果直接算方案数应该是1+1+1+1，但是事实上都是重复的，实际只有一种情况，所以这里就要用到容斥定理了。

要把某个数倍数的情况都从这个小的数里减去（如果把大的置0是不行的，因为这个数可能是多个数的倍数，那它的其他因数的方案就还是重复的了），而且要从大到小枚举，比如上个例子，如果从小到大的话1就被减了多次，其实是不能这样的，而是得把比它大的都处理完才行。

刚开始一直想不出这里容斥原理要怎么用，后来还是看了代码理解的…举个栗子就清楚一点。

对于$2^{f_g}-1$的处理，因为$f_g$非常大，所以可以用欧拉降幂公式或者费马小定理（因为2与MOD互质）。$2^{f_g}\%p=2^{f_gmod(p-1)}\% p$。

要计算期望，分子为$\sum$分数*该分数的方案数，分母为总方案数。

代码：

typedef long long ll;
ll fac[2000010];
ll inv[2000010];
ll f[1000010];
ll sum[1000010];
long long PowerMod(long long a,long long b,long long c)
{
    long long ans=1;
    long long k;
    k=a;
    k=k%c;
    while(b>0)
    {
        if(b&1)
            ans=(ans*k)%c;
        b>>=1;
        k=(k*k)%c;
    }
    return ans;
}
void init()
{
    fac[0]=fac[1]=1;
    for(int i=2;i<=MAXN;i++)
        fac[i]=fac[i-1]*i%MOD;
    inv[MAXN]=PowerMod(fac[MAXN],MOD-2,MOD);
    for(int i=MAXN-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%MOD;
    f[0]=0;f[1]=1;
    for(int i=2;i<=1000000;i++)
        f[i]=(f[i-1]+f[i-2])%(MOD-1);
}
ll calc(int n,int m)
{
    if(n<m)return 0;
    return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
    int t,n,k;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        vector<int>ft;
        for(int i=1;i<=n;i++)//枚举g
            if(n%i==0)ft.push_back(i);
        int len=ft.size();
        for(int i=0;i<len;i++)
            sum[i]=calc(n/ft[i]+k-1,k-1);
        /*for(int i=0;i<len;i++)
            printf("%lld ",sum[i]);
        printf("\n");*/
        for(int i=len-1;i>=0;i--)
            for(int j=i+1;j<len;j++)
            if(ft[j]%ft[i]==0)
                sum[i]=(sum[i]-sum[j]+MOD)%MOD;
        /*for(int i=0;i<len;i++)
            printf("%lld ",sum[i]);
        printf("\n");*/
        ll ans=0;
        for(int i=0;i<len;i++)
            ans=(ans+(((PowerMod(2ll,f[ft[i]]%(MOD-1),MOD)-1)*sum[i])%MOD))%MOD;
        ll tot=calc(n+k-1,k-1);
        ans=(ans*PowerMod(tot,MOD-2,MOD))%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}