题目描述

给定一个长度为 \(n\) 的序列，求长度为 \(k\) 且异或和为 \(0\) 的子序列数量。

形式化题意：

给定一个长度为 \(n\) 的序列 \(a_1, a_2, \dots, a_n\)，求出满足下列条件的 \(k\) 元组 \(\left(b_1, b_2, \dots, b_k\right)\) 数量：

\(1 \le b_1 \lt b_2 \lt \dots \lt b_k \le n\) 并且 \(a_{b_1} \oplus a_{b_2} \oplus \dots \oplus a_{b_k} = 0\)。

\(\oplus\) 表示按位异或运算。

你只需要输出答案在 \(998244353\) 意义下取模的值即可。

输入格式

第一行输入一个整数 \(T\) 表示测试数据组数。

对于每组数据：

首先一行输入两个整数 \(n, k\)。

接下来一行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)。

令 \(N_{tot}\) 表示所有测试组 \(N\) 之和。

\(1 \le T \le 10, N_{tot} \le 10^6\)

对于每组数据：

\(1 \le n \le 10^6, 1 \le k \le 8, 0 \le a_i \le n\)。

请注意对于值域的限制

输出格式

对于每组数据：

输出单行一个整数表示答案在模 \(998244353\) 意义的值。

样例输入

2
6 4
1 3 0 0 2 2
10 5
3 4 5 6 7 5 3 0 1 1

样例输出

5
33