题目背景

题目描述

A 国一共有 $N$ 个城市，编号分别为 $1,2,3,\ldots,N$。

在国家建立之初，政府需要给这 $N$ 个城市之间修一些道路。A 国的国王很喜欢二进制，他首先给每个城市一个数字，第 $i$ 个城市的数字是 $A_i$。之后，对于任意两个城市 $i, j(i < j)$，他会从城市 $i$ 往城市 $j$ 连接 $F(A_i \& A_j)$ 条单向路径。各个符号的含义见题面末尾。

现在国王想知道：从城市 $1$ 出发前往城市 $N$，一共有多少条路径？由于答案可能会很大，你需要输出答案对 $998244353$ 取余数之后的结果。

函数 $F(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数，例如 $F(5)=2, F(15)=4, F(2)=1, F(0)=0$。

$\&$ 表示二进制与运算，二进制与运算的规则是，只有当两个数的对应位都为 $1$ 时，结果才为 $1$；否则结果为 $0$。换句话说，如果某个位上的数都是 $1$，则结果位也为 $1$；否则结果位为 $0$。例如下面的运算：

  10101010
& 11110000
-----------
  10100000

输入格式

第一行输入一个正整数 $T$，表示数据组数。

对于每一组数据，第一行输入一个正整数 $N$，表示城市数。

第二行输入 $N$ 个正整数 $A_1,A_2,\ldots, A_N$。

输出格式

对于每一组数据，输出一行一个整数，表示从城市 $1$ 到城市 $N$ 的路径数，对 $998244353$ 取余数之后的结果。

输入样例

3
4
2 3 3 1
5
1 1 1 1 2
10
213672 382909 212809 216719 213980 121009 213899 220021 289002 120390

输出样例

4
0
12433985

说明提示

样例解释

对于第一组数据，城市道路图如下：

一共有 $4$ 条路径：

• $1 \to 2 \to 4$

• $1\to 3 \to 4$

• $1\to 2 \to 3 \to 4$

• $1\to 2 \to 3 \to 4$

对于第二组数据，$1 \sim 4$ 号城市都与城市 $5$ 没有单向道路，所以路径数是 $0$。

• 对于 20% 的数据，$1\le N \le 5, 1\le A_i < 2^3$

• 对于 50% 的数据，$1\le N \le 1000$

• 对于 100% 的数据，$1\le N \le 2\times 10^5, 1\le T \le 5, 1\le A_i < 2^{30}$。

本站补充：原套别：第 12 套 C 题。