该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本题题面来源于其他平台，不是 ZDZL OJ 原创题

撤硕管理员

题目描述

小A是撤硕管理员。

有 $n$ 个同学想要来上撤硕，邪恶的小A作为撤硕管理员，需要收取一些撤硕的使用费用。

费用“因人而异”，每个同学所需费用由数组 $a$ 表示。如果第 $i$ 个同学上了撤硕，他就需要向小A支付 $a_i$ 的费用。

小A从所有同学中选择任意个同学上撤硕，但他希望他最终收到的撤硕使用费用之和是一个质数。求小A的选择方式总数。

只要在一种选择方式中选择了第 $i$ 个同学，在另一种方案中没有选择第 $i$ 个同学（$1 \le i \le n$），那么我们就认为这两种方案不同。

输入格式

输入两行，第一行包含一个整数 $n$（$1 \le n \le 12$），表示同学的数量。

第二行包含 $n$ 个整数，表示每一个同学的撤硕使用费 $a_i$（$1 \le a_i \le 1000$）。

输出格式

输出一个整数，表示可以使撤硕使用费总和为质数的方案数量。

输入输出样例

输入 #1

4
1 2 2 4

输出 #1

8

说明/提示

样例 1 解释

样例中共有以下 $8$ 种方案：

• $a_1 + a_2 = 1 + 2 = 3$
• $a_1 + a_3 = 1 + 2 = 3$
• $a_1 + a_4 = 1 + 4 = 5$
• $a_1 + a_2 + a_3 = 1 + 2 + 2 = 5$
• $a_1 + a_2 + a_4 = 1 + 2 + 4 = 7$
• $a_1 + a_3 + a_4 = 1 + 2 + 4 = 7$
• $a_2 = 2$
• $a_3 = 2$

数据范围

对于所有测试数据，$1 \le n \le 12$，$1 \le a_i \le 1000$。