You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个神秘的魔法大陆上，存在着$N$座闪耀的城市，它们如同星辰般点缀在大地之上，分别以$1,2,3,\ldots,N$作为其独特的标识。

大陆的魔法师们怀着对二进制魔法的钟爱，赋予每座城市一个独特的魔法数字。第$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}$。