题解

题目描述

小美有一个长度为 $n$ 的序列 $a$，她希望序列中所有元素都是素数。她可以多次进行如下操作：

• 选择一对相邻的数字，将它们合并成一个数，结果为两者的和。

问：最终满足条件的序列（所有元素都是素数）有多少种不同的形态？结果对 $10^9+7$ 取模。

解题思路

问题本质：将序列分割成若干连续子段，使得每个子段的和都是素数，求不同的分割方案数。

题目内容

小美有一个长度为 $n$ 的序列 $a$ ，但小美只对素数感兴趣，因此小美希望 $a$ 中所有的元素都是素数。为此，小美可以做如下的操作任意次：

• 选择一对相邻的数字，将他们合并成一个数，结果为两者的和。

  (形式化的：选择 $i(1≤i<n)$ ，将 $a_i$ 和 $a_{i+1}$ 合并为一个数字，结果是 $a_i+a_{i+1}$ 。

小美想知道，如果要满足她的条件(即所有元素都是素数)，则在她操作完后，$a$ 有多少种可能的形态，请你帮她算一算吧。

(小美认为两个序列 $a,b$ 的最终形态不同，当且仅当两个序列 $a,b$ 的长度不同、或者长度相同且存在 $i$ 使得 $a_i ≠b_i$ 。)

输入描述

本题有多组测试数据。

输入的第一行包含一个正整数 $T(1≤T≤ 100)$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行一个正整数 $n(1≤n≤2000)$ ，表示序列 $a$ 的长度。

第二行 $n$ 个正整数 $a_i(1≤a_i≤2000)$ ，表示序列 $a$

(保证所有测试数据中，$n$ 的总和不超过 $2000$ 。)

输出描述

对于每组测试数据：

在单独的一行输出一个整数，表示最终符合条件的 $a$ 的可能结果。

(由于结果可能很大，因此你只需要输出结果对 $10^9+7$ 取模的值即可。)

样例1

输入

1
5
2 3 2 1 1

输出

5