题目描述

给定一个长度为 $n$ 的非负整数数组 $A_1,A_2,\ldots,A_n$。

对于区间 $l\sim r$，可以执行以下操作：

• 令 $S=0$。
• 按照 $A_l,A_{l+1},\ldots,A_r$ 的顺序，依次将 $S$ 的值增加 $A_i$。

所有加法均按照普通的二进制加法进行，在一次二进制加法中，如果某一位向更高一位产生了一个进位，就称其发生了一次“进位”。不同二进制位产生的进位分别计算，同一次加法中发生的多次连续进位也分别计算。用 $C(l,r)$ 表示区间 $l\sim r$ 执行上述操作过程中发生的“进位”总数。

例如计算 $3+5$：$3=011_2$，$5=101_2$，相加得 $1000_2$。从低位到高位分别在第 $0,1,2$ 位产生进位，共 $3$ 次进位。若发生连续进位，例如 $7+1=111_2+1_2=1000_2$，从第 $0$ 位到第 $2$ 位连续产生 $3$ 次进位，也分别计入。

若一个长度为 $m$ 的数组 $[p_1,p_2,\ldots,p_m]$ 满足以下条件，则称其合法：

• $m>0$
• 对任意 $1\le i\le m$，均满足 $1\le p_i\le n$
• 对任意 $1\le i< m$，均满足 $p_i<p_{i+1}$ 且 $C(p_i,p_{i+1})=1$

两个数组不同，当且仅当两个数组长度不同，或至少一个位置的数字的不同。

求有多少个不同的合法数组，答案对 $998,244,353$ 取模。

输入格式

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

对于每组测试数据，输入两行：

• 第一行输入一个整数 $n$。
• 第二行输入 $n$ 个非负整数 $A_1,A_2,\ldots,A_n$。

输出格式

对于每组测试数据，输出一行一个非负整数，表示合法数组数量对 $998,244,353$ 取模后的结果。

3
5
1 4 4 3 8
6
6 3 7 4 6 6
5
52843137796 640771484120 983154867810 489455928042 397256148081

8
9
5

提示

【样例 1 解释】

第一组数据合法下标序列为 $[1]$, $[2]$, $[3]$, $[4]$, $[5]$, $[1,3]$, $[2,3]$, $[2,4]$，共 $8$ 个。

第二组数据合法下标序列为 $[1]$, $[2]$, $[3]$, $[4]$, $[5]$, $[6]$, $[3,4]$, $[4,5]$, $[3,4,5]$，共 $9$ 个。

第三组数据合法下标序列为 $[1]$, $[2]$, $[3]$, $[4]$, $[5]$，共 $5$ 个。

【样例 2】

见选手目录下的 carry/carry2.in 与 carry/carry2.ans。

该样例满足测试点 $3 \sim 5$ 的限制。

【样例 3】

见选手目录下的 carry/carry3.in 与 carry/carry3.ans。

该样例满足测试点 $6 \sim 8$ 的限制。

【样例 4】

见选手目录下的 carry/carry4.in 与 carry/carry4.ans。

该样例满足测试点 $9 \sim 14$ 的限制。

【样例 5】

见选手目录下的 carry/carry5.in 与 carry/carry5.ans。

该样例满足测试点 $15 \sim 16$ 的限制。

【样例 6】

见选手目录下的 carry/carry6.in 与 carry/carry6.ans。

该样例满足测试点 $17 \sim 20$ 的限制。

【数据范围】

对于所有测试点，保证：

• $1\le T\le 30$
• $1\le n\le 5\times10^5$
• $0\le A_i\le 10^{12}$
• $\sum n\le 6\times10^6$

其中，$\sum n$ 表示一个输入文件内所有测试数据中 $n$ 的总和。

测试点编号	$n \le$	$\sum n \le$
$1,2$	$10$	$300$
$3\sim 5$	$2\times 10^3$	$3\times 10^3$
$6\sim 8$	$5\times 10^3$	$10^4$
$9\sim 14$	$10^5$	$5\times10^5$
$15\sim 16$	$2\times 10^5$	$2\times 10^6$
$17\sim 20$	$5\times 10^5$	$6\times 10^6$

【提示】

在本题中，你可能需要快速求出一个整数在二进制表示下有多少位为 $1$。你可以使用如下内建函数：

• __builtin_popcount(x)：返回 $x$ 的二进制表示中 $1$ 的个数，参数 $x$ 通常为 int 或 unsigned int 类型。
• __builtin_popcountll(x)：返回 $x$ 的二进制表示中 $1$ 的个数，参数 $x$ 通常为 long long 或 unsigned long long 类型。

二者的时间复杂度均为 $O(1)$。

注意：本题输入量较大，建议选手使用较快的读入方式，以避免因输入耗时影响程序效率。