给定一个长度为 的只包含 和 的序列 ()。你可以进行若干次如下操作：
例如若序列 ，选择对 进行操作，操作后序列会变为 。
求在进行若干次操作后，能产生多少种本质不同的序列，输出结果对 的结果。两个序列不同当且仅当它们的长度不同或某个数不同。
可能很大，因此序列会通过将相同数字压缩成同一段的格式输入。特别地，保证每一段相同数字的长度，从前往后单调不降。
第一行输入一个整数 ()，表示测试数据组数。
接下来依次给出每组测试数据，对于每组测试数据：
第一行输入两个整数 () 表示序列分成的段数，以及 的值。
第二行输入 个整数 ()，其中 表示序列中第 段数的长度。
由于相邻的段内数的值不同，故可以通过 和 唯一确定这个长度为 的序列。
保证所有数据中的 。
对于每组数据，输出一个整数表示答案对 取模的结果。
2 3 1 1 1 2 8 2 1 2 3 4 5 6 7 8
7 2961300
样例一中第一组测试数据表示的序列为 ，进行若干次操作后能表示出的本质不同的序列有：
