小苯的糖果游戏

题号：NC285708
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯和格格正在玩一款名为“吃糖果”的游戏，游戏的过程是这样的：
两人面前有 $n$ 堆糖果，从左到右编号从 $1$ 到 $n$ ，其中第 $i$ 堆糖果中有 $a_i$ 颗糖果。初始时小苯在 $0$ 号位置（第一堆糖果的左侧），格格在 $n+1$ 号位置。（第 $n$ 堆糖果的右侧）

假设小苯目前位于 $i$ 号糖果堆的位置，格格位于 $j$ 号糖果堆（ $i<j-1$ ），则每秒钟都会发生如下过程：
$\bullet$ 如果 $i = j -1$ （即两人已经相邻），则游戏结束。
否则，两人轮流操作，小苯先手：
$\ \ \bullet$ 轮到小苯时，小苯可以选择待在原地；或跳跃到 $i+1$ 号糖果堆，然后选择吃掉所有 $a_{i+1}$ 颗糖果，或者不吃。
$\ \ \bullet$ 轮到格格时，格格可以选择待在原地；或跳跃到 $j-1$ 号糖果堆，然后选择吃掉所有 $a_{j-1}$ 颗糖果，或者不吃。

（当然，吃掉某堆糖果的前提是此堆糖果之前没被吃掉。换句话说每堆糖果被任何人吃掉后都会消失。）

现在我们考虑所有结束的游戏，为了公平起见，小苯希望自己和格格吃掉的糖果数量相同，他想知道有多少种不同的游戏过程能满足他的要求，请你帮他算一算吧。

（游戏过程的不同性在下方备注处给出了定义。）

输入描述:

本题含有多组测试数据。
第一行一个正整数 ，表示测试数据的组数。
接下来对于每组测试数据，输入包含两行。
第一行一个正整数 ，表示糖果的总堆数。
第二行  个正整数 ，表示每堆糖果的总个数。

输出描述:

对于每组测试数据，输出一行一个整数，表示不同的游戏过程数。
（由于结果可能很大，因此你只要输出答案对  取模的值即可。）

示例1

输入

复制

2
3
1 2 1
6
1 3 1 1 2 1

输出

复制

6
41

说明

考虑第一组测试数据，最终结束时满足小苯要求的，不同的游戏过程有：
小苯位于 ，格格位于 ，两人都没有吃糖果。
小苯位于 ，格格位于 ，两人都没有吃糖果。
小苯位于 ，格格位于 ，两人都没有吃糖果。
小苯位于 ，格格位于 ，两人都没有吃糖果。
小苯位于 ，格格位于 ，小苯选择吃掉的糖果编号集合为：，格格选择吃掉的糖果编号集合为 。
小苯位于 ，格格位于 ，小苯选择吃掉的糖果编号集合为：，格格选择吃掉的糖果编号集合为 。

备注:

考虑两个游戏过程：
游戏过程 ： 结束时，小苯位于 ，小苯选择拿走的糖果堆的编号集合为 ，格格选择拿走的糖果堆编号集合为 。
游戏过程 ： 结束时，小苯位于 ，小苯选择拿走的糖果堆的编号集合为 ，格格选择拿走的糖果堆编号集合为 。
定义两个游戏过程相同，当且仅当：，同时  且 。
否则两个游戏过程不相同。