AT_arc224_f.AND/OR

You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$ and an integer $K$.

Initially, $x=0$. For $i=1,2,\dots,N$ in this order, let us choose one of the following two operations to perform.

• Operation $1$ : Replace $x$ with $x$ ${\rm AND}$ $A_i$.
• Operation $2$ : Replace $x$ with $x$ ${\rm OR}$ $A_i$.

Here, operation $2$ must be chosen at most $K$ times in total. ${\rm AND}$ denotes the bitwise ${\rm AND}$ operation, and ${\rm OR}$ denotes the bitwise ${\rm OR}$ operation.

Let $M$ be the maximum possible value of $x$ after all operations are finished. Find the number, modulo $998244353$, of operation sequences such that the final $x$ equals $M$.

Here, two operation sequences are distinguished if and only if there exists an integer $j$ ($1 \le j \le N$) such that the operation chosen at the $j$-th step differs between them.

$T$ test cases are given; solve each of them.

What is the bitwise $\mathrm{AND}$ operation?

The bitwise $\mathrm{AND}$ of non-negative integers $A, B$, denoted $A\ \mathrm{AND}\ B$, is defined as follows.

• The digit in the $2^k$ ($k \geq 0$) place of the binary representation of $A\ \mathrm{AND}\ B$ is $1$ if the corresponding digits of $A$ and $B$ in binary are both $1$, and $0$ otherwise.

For example, $3\ \mathrm{AND}\ 5 = 1$ (in binary: $011\ \mathrm{AND}\ 101 = 001$).

What is the bitwise $\mathrm{OR}$ operation?

The bitwise $\mathrm{OR}$ of non-negative integers $A, B$, denoted $A\ \mathrm{OR}\ B$, is defined as follows.

• The digit in the $2^k$ ($k \geq 0$) place of the binary representation of $A\ \mathrm{OR}\ B$ is $1$ if at least one of the corresponding digits of $A$ and $B$ in binary is $1$, and $0$ otherwise.

For example, $3\ \mathrm{OR}\ 5 = 7$ (in binary: $011\ \mathrm{OR}\ 101 = 111$).

给你一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$ 和一个整数 $K$。

初始时，$x=0$。按顺序对 $i=1,2,\dots,N$ 执行以下两种操作之一：

• 操作 $1$：将 $x$ 替换为 $x\ \mathrm{AND}\ A_i$；
• 操作 $2$：将 $x$ 替换为 $x\ \mathrm{OR}\ A_i$。

其中，操作 $2$ 在整个过程中至多可执行 $K$ 次。$\mathrm{AND}$ 表示按位与（bitwise AND）运算，$\mathrm{OR}$ 表示按位或（bitwise OR）运算。

令 $M$ 为所有操作完成后 $x$ 可能达到的最大值。求最终 $x$ 恰好等于 $M$ 的操作序列的个数（对 $998244353$ 取模）。

此处，若存在某个整数 $j$（$1 \le j \le N$），使得两个操作序列在第 $j$ 步所选操作不同，则认为这两个操作序列互不相同。

共给出 $T$ 组测试用例，请分别求解。

什么是按位 $\mathrm{AND}$ 运算？

非负整数 $A, B$ 的按位 $\mathrm{AND}$ 运算，记作 $A\ \mathrm{AND}\ B$，定义如下：

• $A\ \mathrm{AND}\ B$ 的二进制表示中，$2^k$ 位（$k \geq 0$）上的数字为 $1$，当且仅当 $A$ 与 $B$ 的二进制表示中对应位均为 $1$；否则该位为 $0$。

例如，$3\ \mathrm{AND}\ 5 = 1$（二进制：$011\ \mathrm{AND}\ 101 = 001$）。

什么是按位 $\mathrm{OR}$ 运算？

非负整数 $A, B$ 的按位 $\mathrm{OR}$ 运算，记作 $A\ \mathrm{OR}\ B$，定义如下：

• $A\ \mathrm{OR}\ B$ 的二进制表示中，$2^k$ 位（$k \geq 0$）上的数字为 $1$，当且仅当 $A$ 与 $B$ 的二进制表示中对应位至少有一个为 $1$；否则该位为 $0$。

例如，$3\ \mathrm{OR}\ 5 = 7$（二进制：$011\ \mathrm{OR}\ 101 = 111$）。

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
This input contains five test cases.

For the first test case, $M=7$, and the following three operation sequences achieve the final value $x=M$.

• Perform the operations in the order $1,1,2,2,2$. $x$ changes as $0 \to 0 \to 0 \to 1 \to 3 \to 7$.
• Perform the operations in the order $1,2,1,2,2$. $x$ changes as $0 \to 0 \to 7 \to 1 \to 3 \to 7$.
• Perform the operations in the order $2,1,1,2,2$. $x$ changes as $0 \to 3 \to 3 \to 1 \to 3 \to 7$.

For the fifth test case, note that the answer should be output modulo $998244353$.

Constraints

• $1 \le T \le 10^4$
• $1 \le K \le N \le 2 \times 10^5$
• $0 \le A_i < 2^{60}$
• The sum of $N$ in each input is at most $2 \times 10^5$.
• All input values are integers.

样例 1 解释：
该输入包含五个测试用例。

对于第一个测试用例，$M=7$，以下三种操作序列均可使最终值 $x=M$ 成立：

• 按顺序执行操作 $1,1,2,2,2$。$x$ 的变化过程为 $0 \to 0 \to 0 \to 1 \to 3 \to 7$。
• 按顺序执行操作 $1,2,1,2,2$。$x$ 的变化过程为 $0 \to 0 \to 7 \to 1 \to 3 \to 7$。
• 按顺序执行操作 $2,1,1,2,2$。$x$ 的变化过程为 $0 \to 3 \to 3 \to 1 \to 3 \to 7$。

对于第五个测试用例，请注意答案需对 $998244353$ 取模输出。

约束条件

• $1 \le T \le 10^4$
• $1 \le K \le N \le 2 \times 10^5$
• $0 \le A_i < 2^{60}$
• 所有输入中 $N$ 的总和不超过 $2 \times 10^5$。
• 所有输入值均为整数。