Background

Original link: https://oier.team/problems/X2D。

Hey, if we could throw everything away,
Hey, if we could throw everything away.

Would living with a smile become easier?
Would living with a smile become easier?

Problem Description

Given two positive integers $n, k$。

Define $\displaystyle f(x)=\sum_{i=1}^x \gcd(i,i\oplus x)^k$。Compute $\displaystyle \sum_{i=1}^n f(i)$。Here, $\gcd(a,b)$ denotes the greatest common divisor of $a$ and $b$, and $\oplus$ denotes bitwise XOR, i.e. ^ in C++。

Since the answer may be very large, you only need to output the result modulo $10^9+7$。

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

Then each test case follows. For each test case, input one line with two positive integers $n, k$。

Output Format

For each test case, output one line with one integer, representing the answer modulo $10^9+7$。

5
3 2
10 1
261 261
2333 2333
124218 998244353

17
134
28873779
470507314
428587718

Hint

[Sample Explanation]

For the $1$-st test case:

$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$。

[Constraints]

For all test cases, $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$。

This problem uses bundled testdata.

Let $\sum n$ denote the sum of $n$ within a single test point.

• 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): no special constraints。

Translated by ChatGPT 5