题目描述

盖亚为了抵御邪恶敌人的进攻，必须建立一个防护罩。防护罩可以由若干个魔力水晶组成，每个魔力水晶有一定的魔力值，而防护罩的总魔力值为所有魔力水晶魔力值之和。 盖亚发现只有当防护罩的总魔力为质数时，才可以保证防护罩的正常运转。现在盖亚有 $n$ 个魔力水晶，并且知道每个魔力水晶的魔力值 $a_i$ 。他想知道他有多少种构建防护罩的方案。 假设所有魔力水晶除魔力值以外全部相同。也就是说只有如果两个方案不同，当且仅当每个方案的水晶的魔力值从小到大排序后的序列不同。

输入格式

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

输出格式

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

4

1 2 2 4

5