观察到 $k=0$ 时答案为 $2^n-1$，$k=1$ 时答案为 $(n+1)(2^n-1)$。使用快速幂即可，时间复杂度 $O(T \log n)$。

进一步地，可以把指数对 $p - 1$ 取模后先做光速幂，时间复杂度 $O(\sqrt{p} + T)$。

#include <bits/stdc++.h>
using namespace std;
long long p[32];
const int P = 998244353;
long long power(int x, long long y)
{
	y %= P - 1;
	long long ans = 1;
	for (int i = 29; i >= 0; i--)
		if (y & (1 << i)) ans = ans * p[i] % P;
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	p[0] = 2;
	for (int i = 1; i <= 30; i++)
		p[i] = p[i - 1] * p[i - 1] % P;
	int T;
	cin >> T;
	while (T--)
	{
		long long n, k;
		cin >> n >> k;
		if (k == 0) cout << power(2, n) - 1 << '\n';
		if (k == 1) cout << (n + 1) % P * (power(2, n) - 1) % P << '\n';
	}
	return 0;
}