【MX-X2-T4】「Cfz Round 4」Gcd with Xor

ねえ もしも全て投げ捨てられたら 呐 若然能将一切舍弃的话 笑って生きることが楽になるの 笑着活下去这样的事就会变的轻松吗

给定两个正整数 $n,k$。 定义 $\displaystyle f(x)=\sum_{i=1}^x \gcd(i,i\oplus x)^k$。计算 $\displaystyle \sum_{i=1}^n f(i)$。其中 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公因数，$\oplus$ 表示**按位异或**，即 C++ 中的 `^`。 由于答案可能很大，所以你只需要输出答案对 $10^9+7$ 取模的结果。

**本题有多组测试数据。** 输入的第一行包含一个整数 $T$，表示测试数据组数。 接下来依次输入每组测试数据。对于每组测试数据，输入一行两个正整数 $n,k$。

对于每组测试数据，输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。

5
3 2
10 1
261 261
2333 2333
124218 998244353

17
134
28873779
470507314
428587718

**【样例解释】** 对于第 $1$ 组测试数据： $f(1)=\gcd(1,0)^2=1$。 $f(2)=\gcd(1,3)^2+\gcd(2,0)^2=5$。 $f(3)=\gcd(1,2)^2+\gcd(2,1)^2+\gcd(3,0)^2=11$。 $f(1)+f(2)+f(3)=17$。 **【数据范围】** 对于所有测试数据，$1\le T\le 1000$，$1\le n\le 2\times 10^5$，$\sum n\le 2\times 10^5$，$1\le k\le 10^9$。 **本题采用捆绑测试。** 设 $\sum n$ 表示单个测试点中 $n$ 的和。 - Subtask 1（10 points）：$\sum n\le 2000$。 - Subtask 2（12 points）：$\sum n\le 10^4$。 - Subtask 3（15 points）：$k=1$。 - Subtask 4（45 points）：$\sum n\le 10^5$。 - Subtask 5（18 points）：无特殊限制。