#T1174. 组合质数

组合质数

题目描述

33DAI 想从 nn 个不同的数中选取一些数,使这些数的和为质数,请问 33DAI 有多少种选择方法?

(如果两种方案选出来的数相同,就认为是同一种方案)

输入格式

输入第一行为一个整数 nn,表示有 nn 个数。

接下来一行为空格隔开的 nn 个正整数,表示这 nn 个数。

输出格式

输出一行,为一个整数,即有多少种选择方案可以选一组数使得和为质数。

样例

3
1 2 3
4
5
1 2 3 4 5
12

样例 1 说明

231+2=32+3=52、3、1+2=3、2+3=544 种方案

数据范围

对于 60%60\% 的数据:1n31\le n\le 3

对于 100%100\% 的数据:1n201每个数5×1041\le n \le 20,1\le 每个数 \le 5\times 10^4