【MX-X2-T4】「Cfz Round 4」Gcd with Xor
题目背景
原题链接：<https://oier.team/problems/X2D>。
---
ねえ もしも全て投げ捨てられたら
呐 若然能将一切舍弃的话
笑って生きることが楽になるの
笑着活下去这样的事就会变的轻松吗
题目描述
给定两个正整数 $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$ 取模的结果。
输入输出样例
输入样例 #1
5
3 2
10 1
261 261
2333 2333
124218 998244353输出样例 #1
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）：无特殊限制。