题目背景

ねえ もしも全て投げ捨てられたら
呐 若然能将一切舍弃的话

笑って生きることが楽になるの
笑着活下去这样的事就会变的轻松吗

题目描述

给定两个正整数 $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）：无特殊限制。