まず、 \(1\) 以上 \(2^M\) 未満のある値 \(x\) を取り、\(A\leftarrow(A_1\oplus x,A_2\oplus x,\ldots,A_N\oplus x)\) としても \(A\) が条件を満たすかどうかは変わりません。したがって、 \(A_1=0\) と条件を追加した際の通り数に \(2^M\) を掛けた値が答えとなります。以降は \(A_1=0\) と条件を追加した場合を考えます。

\(A_1=0\) より、各 \(i\) に対し \(\operatorname{popcount}(A_i)\le 2\) となります。

\(S=\left\lbrace A_i \ |\ \operatorname{popcount}(A_i)= 2\right\rbrace\) とします。

[1] \(|S|=0\) のとき

全ての \(i\) に対し \(\operatorname{popcount}(A_i)\le 1 \) です。このとき、\(\operatorname{popcount}(A_i\oplus A_j)\le \operatorname{popcount}(A_i)+\operatorname{popcount}(A_j)\le 2\) が成立するため条件は \(\operatorname{popcount}(A_i)\le 1 \) のみです。この条件を満たす \(A\) は \((M+1)^{N-1}\) 通りあります。

[2] \(|S|=1\) のとき

\(S=\lbrace X\rbrace\) とします。

もし \(\operatorname{popcount}(A_i)=1\) なら \(A_i\) で立っている唯一のビットは \(X\) でも立っている必要があります。逆に、全ての \(i\) に対し上の条件が成り立てば \(A\) は条件を満たします。したがって、

• \(X\) の決め方は \(\displaystyle \binom M2\) 通り
• \(\operatorname{popcount}(A_i)\le 1\) を満たす \(A_i\) は \(3\) 通り
• \(\operatorname{popcount}(A_i)=2\) を満たす \(A_i\) は \(1\) 通り
• \(\operatorname{popcount}(A_i)=2\) を満たす \(A_i\) は \(1\) つ以上存在する必要がある

より条件を満たす \(A\) は \(\displaystyle \binom M2(4^{N-1} - 3^{N-1})\) 通りです。

[3] \(|S|\geq 2\) のとき

[3-a] \(S\) の総 bit AND が \(0\) のとき

この場合、 \(3\) つの正整数 \(k_1 < k_2 < k_3\) を用いて \(S=\left\lbrace 2^{k_1} + 2^{k_2} , 2^{k_1} + 2^{k_3} , 2^{k_2} + 2^{k_3} \right\rbrace\) と表されます。したがって、

• \(k_1,k_2,k_3\) の決め方は \(\displaystyle \binom M3\) 通り
• \(A_i\) として許される値は \(0,2^{k_1} + 2^{k_2} , 2^{k_1} + 2^{k_3} , 2^{k_2} + 2^{k_3} \) の \(4\) 通り
• \(A_i=2^{k_1} + 2^{k_2} , 2^{k_1} + 2^{k_3} , 2^{k_2} + 2^{k_3} \) は全て \(1\) つ以上存在する

より条件を満たす \(A\) は\(\displaystyle \binom M3(4^{N-1}-3\times 3^{N-1}+3\times 2^{N-1}-1)\) 通りであることが分かります。

[3-b] \(S\) の総 bit AND が \(0\) でないとき

\(S\) の全ての要素があるビット（\(2^k\) とする）を共有している場合を考えます。このとき、 \(x,y \in S\) なら \(\operatorname{popcount}(x\oplus y)\le 2\) が成り立ちます。

\(k'\neq k\) ならある \(x \in S\) が存在し \(\operatorname{popcount}(2^{k'}\oplus x)> 2\) が成り立ち、逆に全ての \(x\in S\) に対し \(\operatorname{popcount}(2^{k}\oplus x) \le 2\) が成り立ちます。このことから、 \(\operatorname{popcount}(A_i)=1\) なら \(A_i=2^k\) が分かります。

したがって、

• \(k\) の決め方は \(M\) 通り
• \(\operatorname{popcount}(A_i)=2\) となる \(A_i\) の種類数は \(M-1\) 通り
• \(\operatorname{popcount}(A_i)\le 1\) となる \(A_i\) の種類数は \(2\) 通り
• \(\operatorname{popcount}(A_i)=2\) となる \(A_i\) は \(2\) つ以上存在する

より条件を満たす \(A\) は \(\displaystyle M\left((M+1)^{N-1} - 2^{N- 1} - (M-1)(3^{N-1}-2^{N-1})\right)\) 通りです。

以上をまとめて適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(\log N)\) です。

実装例(Python3)

mod = 998244353
two_inv = pow(2, mod - 2, mod)
six_inv = pow(6, mod - 2, mod)


def c2(n):
    return n * (n - 1) % mod * two_inv % mod


def c3(n):
    return n * (n - 1) % mod * (n - 2) % mod * six_inv % mod


def solve(n, m):
    n2 = pow(2, n - 1, mod)
    n3 = pow(3, n - 1, mod)
    n4 = pow(4, n - 1, mod)
    nm1 = pow(m + 1, n - 1, mod)
    ans = 0
    # 0
    ans += nm1
    # 1
    ans += c2(m) * (n4 - n3) % mod
    # 2
    ko = n4 - 3 * n3 + 3 * n2 - 1
    ans += c3(m) * ko % mod
    # >= 2
    ko = nm1 - n2 - (m - 1) * (n3 - n2)
    ans += m * ko % mod
    ans %= mod
    ans *= pow(2, m, mod)
    ans %= mod
    return ans

for _ in range(int(input())):
    n, m = map(int, input().split())
    print(solve(n, m))