题目描述

盖亚为了抵御邪恶敌人的进攻，必须建立一个防护罩。防护罩可以由若干个魔力水晶组成，每个魔力水晶有一定的魔力值，而防护罩的总魔力值为所有魔力水晶魔力值之和。 盖亚发现只有当防护罩的总魔力为质数时，才可以保证防护罩的正常运转。现在盖亚有 $n$ 个魔力水晶，并且知道每个魔力水晶的魔力值 $a_i$ 。他想知道他有多少种构建防护罩的方案。 假设所有魔力水晶都是不同的。只要在一种方案中选择了第 $i$ 个魔力水晶，在另一种方案中没有选择第 $i$ 个魔力水晶$(1\leq i \leq n)$ ，那么我们就认为这两种方案不同。

输入格式

输入两行，第一行包含一个整数 $n(1\leq n \leq 12)$ ，表示魔力水晶的数量。 第二行包含 $n$ 个整数，表示每一个魔力水晶的魔力值 $a_i(1\leq a_i \leq 1000)$。

输出格式

输出一个整数，表示可以组成质数的方案数量。

4

1 2 2 4

8