C-小苯的数字合并_牛客周赛 Round 108

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$ ，他可以对 $a$ 进行任意次“数字合并”操作，具体地，一次数字合并操作描述为：
$\hspace{23pt}\bullet\,$ 选择一个下标 $i\left(1 \leqq i< |a|\right)$ ，将 $a_i$ 和 $a_{i+1}$ 合并为一个数字，结果为两个的和 $a_i+a_{i+1}$ 。合并后数组长度减 $1$ ，下标按新数组重新编号。
$\hspace{15pt}$ 现在小苯可以进行任意次上述操作，他想知道他可以得到多少种本质不同结果数组，请你帮他数一数吧。换句话说，在可以进行任意次操作的情况下，所有可能得到的数组 $a$ 有多少种本质不同的模样。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

$\hspace{15pt}$ 小苯认为两个数组 $a,b$ 本质不同，当且仅当以下两个条件至少满足其中之一：
$\hspace{23pt}\bullet\,$ 两个数组的长度不同;
$\hspace{23pt}\bullet\,$ 两个数组的长度相同，但存在至少一个 $i\left(1 \leqq i \leqq |a|\right)$ ，使得 $a_i \neq b_i$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示数组  的长度。
第二行输入  个整数 ，表示数组中的元素。
除此之外，保证所有测试数据中， 的总和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示最终本质不同结果数组的个数对  取模后的值。

示例1

输入

复制

输出

复制

2
1

说明

对于第一组测试数据，有两种操作方案：
不操作，数组就是 ；
操作一次选择 ，数组变为：。
因此最终的结果数组有  种。

对于第二组测试数据，显然无法操作，因此最终的结果数组只有一种。