小苯有一个长度为 的数组 ，他可以对 进行任意次“数字合并”操作，具体地，一次数字合并操作描述为： 选择一个下标 ，将 和 合并为一个数字，结果为两个的和 。合并后数组长度减 ，下标按新数组重新编号。 现在小苯可以进行任意次上述操作，他想知道他可以得到多少种本质不同结果数组，请你帮他数一数吧。换句话说，在可以进行任意次操作的情况下，所有可能得到的数组 有多少种本质不同的模样。由于答案可能很大，请将答案对 取模后输出。 小苯认为两个数组 本质不同，当且仅当以下两个条件至少满足其中之一： 两个数组的长度不同; 两个数组的长度相同，但存在至少一个 ，使得 。

输入描述:

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

输出描述:

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