P10855 [MX-X2-T4] "Cfz Round 4" Gcd with Xor

Original link: 。 --- 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?

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

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

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

**[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