考虑枚举 $\gcd$，答案即为：

$$\sum\limits_{g = 1} ^ n g^k\sum\limits_{x = 1}^{n}\sum\limits_{i = 1}^{x}[\gcd(i, i\oplus x) = g] $$

调换求和顺序，枚举 $i$ 为 $g$ 的倍数得到：

$$\begin{aligned} &\sum\limits_{g = 1} ^ n g^k\sum\limits_{i = 1}^{\lfloor \frac{n}{g}\rfloor}\sum\limits_{x = ig}^{n}[\gcd(ig, ig\oplus x) = g]\\ =&\sum\limits_{g = 1} ^ n g^k\sum\limits_{i = 1}^{\lfloor \frac{n}{g}\rfloor}\sum\limits_{x = ig}^{n}[g \mid ig\oplus x][\gcd(i, \frac{ig\oplus x}{g}) = 1] \end{aligned} $$

上莫反，得：

$$\begin{aligned} &\sum\limits_{g = 1} ^ n g^k\sum\limits_{i = 1}^{\lfloor \frac{n}{g}\rfloor}\sum\limits_{x = ig}^{n}[g \mid ig\oplus x]\sum\limits_d [d \mid i][d \mid \frac{ig\oplus x}{g}]\mu(d)\\ =&\sum\limits_{g = 1} ^ n g^k\sum\limits_{d = 1}^{\lfloor\frac{n}{g}\rfloor}\mu(d)\sum\limits_{i = 1}^{\lfloor \frac{n}{gd}\rfloor}\sum\limits_{x = ig}^{n}[gd \mid igd\oplus x] \end{aligned} $$

令 $T = gd$，枚举 $T$ 得：

$$\begin{aligned} &\sum\limits_{g = 1} ^ n g^k\sum\limits_{d = 1}^{\lfloor\frac{n}{g}\rfloor}\mu(d)\sum\limits_{i = 1}^{\lfloor \frac{n}{T}\rfloor}\sum\limits_{x = iT}^{n}[T \mid iT\oplus x] \\ =&\sum\limits_{T = 1} ^ n \sum\limits_{g \mid T} g^k\mu(\frac{T}{g})\sum\limits_{i = 1}^{\lfloor \frac{n}{T}\rfloor}\sum\limits_{x = iT}^{n}[T \mid iT\oplus x] \end{aligned} $$

记 $\displaystyle f(T) = \sum\limits_{g \mid T} g^k\mu(\frac{T}{g}), g(i, T) = \sum\limits_{x = iT}^{n}[T \mid iT\oplus x]$，于是答案为：

$$\sum\limits_{T = 1} ^ n f(T)\sum\limits_{i = 1}^{\lfloor \frac{n}{T}\rfloor}g(i, T) $$

$f(T)$ 可以简单预处理出来，问题在于如何快速求 $g(i, T)$。

先将 $g$ 做个变形：$\displaystyle g(i, T) = \sum\limits_{x}[iT\leq x\leq n][T\mid iT\oplus x]$，我们考虑如何计算满足条件的 $x$ 个数。

前面的东西可以拆成两个前缀相减，于是我们只用解决如何计算 $\displaystyle \sum\limits_{x = 1}^n[T\mid iT\oplus x]$。

我们考虑对 $n$ 做类似数位 dp 的东西，枚举当前位 $b$，发现当 $n$ 二进制下第 $b$ 位为 $1$ 时，我们往 $x$ 这一位填 $0$，前面的几位和 $n$ 保持一致（记当前形成的数为 $c$），此时后面的位置可以随便填，也就是合法的 $x$ 形成了一段 $[c, c + 2 ^ {b})$ 的区间，此时我们将其异或上 $iT$ 后，得到的还是一段长度为 $2 ^ {b}$ 的连续区间，然后就可以 $\mathcal{O}(1)$ 计算出该连续区间内有多少 $T$ 的倍数。

加上外层的调和级数枚举，总时间复杂度为 $\mathcal{O}(n\ln n\log n)$。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 5;

using Z = ModInt<(int)1e9 + 7>;

int T, n, k, tot, prime[N], mu[N];
bool isp[N];
std::vector<int> d[N];
Z F[N], pw[N];

void sieve(int n) {
	memset(isp, true, sizeof(isp));
	isp[0] = isp[1] = false; mu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (isp[i]) prime[++tot] = i, mu[i] = -1;
		for (int j = 1; j <= tot && 1ll * i * prime[j] <= n; j++) {
			int p = prime[j]; isp[i * p] = false;
			if (i % p == 0) {
				mu[i * p] = 0;
				break;	
			}
			else mu[i * p] = -mu[i];
		}
	}
	for (int i = 1; i <= n; i++) pw[i] = power(Z(i), k);
	for (int i = 1; i <= n; i++) {
		F[i] = 0;
		for (auto g : d[i]) F[i] += pw[g] * mu[i / g];
	}
}

int calc(int l, int r, int x) {
	if (l == 0) return r / x + 1;
	return r / x - (l - 1) / x;
}

Z G(int n, int i, int T) {
	int a = i * T;
	Z ret = ((n ^ a) % T == 0);
	for (int i = 18; i >= 0; i--) if (n >> i & 1) {
		int c = (n >> (i + 1) << (i + 1)), d = (a >> i << i), e = c ^ d;
		ret += calc(e, e + (1 << i) - 1, T);
	}
	return ret;
}

void solve() {
	std::cin >> n >> k; sieve(n);

	Z ans = 0;
	for (int T = 1; T <= n; T++) {
		Z res = 0;
		for (int i = 1; i <= n / T; i++) 
            res += G(n, i, T) - G(i * T - 1, i, T);
		ans += F[T] * res;
	}
	std::cout << ans << "\n";
}

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	for (int i = 1; i < N; i++) 
        for (int j = i; j < N; j += i) 
            d[j].push_back(i);

	std::cin >> T;
	while (T--) solve();

	return 0;
}