题目描述

你有 $N$ 本书和一个 $K$ 层的书架。

随机地将 $N$ 本书放进书架,这个时候第 $i$ 层的书本数量为 $cnt_i$。

令 $f_i$ 为第 $i$ 个 $Fibonacci$ 数($f_0=0, f_1=1, f_2=1, f_i=f_{i-1}+f_{i-2}$)。

令第 $i$ 层的美丽值 $beauty_i=2^{f_{cnt_i}}-1$,

则这个书架的总得分 $score=gcd(beauty_1, beauty_2, beauty_3, …, beauty_K)$。

现在给定 $N$ 和 $K$,求书架的得分的期望值。

输入和输出

输入

第一行是一个不超过 10 的正整数 $T$,代表有 $T$ 组测试数据。

接下来 $T$ 行,每行包含两个整数 $N, K$ ($0 < N, K leq 10^6$)。

输出

一共 $T$ 行。对于每一组数据,输出答案在模 $10^9+7$ 意义下的值。

样例

输入

输出

思路

我们知道, $gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$ 。

所以我们就可以将 $gcd(beauty_1, beauty_2, beauty_3, …, beauty_k)$ 转化为 $2^{gcd(f_{cnt_1},f_{cnt_2},…,f_{cnt_k},)}-1$。

我们也可以轻易地证明 $gcd(f_x,f_y)=f_{gcd(x,y)}$。

所以我们最终得到了这个公式

$2^{f_{gcd(cnt_1,cnt_2,…,cnt_k}}-1$。

枚举每个可能的 $gcd$, 计算它的贡献。莫比乌斯反演即可。

首先,将 $N$ 分成 $K$ 个 $gcd$ 的倍数有 $C_{frac n{gcd}+k-1}^{k-1}$ 种方案,所以每个 $gcd$ 对答案的贡献为 $C_{frac n{gcd}+k-1}^{k-1} imes (2^{f_{gcd}}-1)$。

为了避免重复计算,使用莫比乌斯系数容斥。

没了。

代码