题目描述

千夜老师想从 $n$ 个不同的数中选取一些数，假设选取了 $k$ 个数，选区的第 $i$ 个数为 $a_i$，那么千夜老师会算出

$$X=a_1+2a_2+3a_3+...+ia_i+...+(k-1)a_{k-1}+ka_k$$

千夜老师希望 $X$ 为质数，请问千夜老师有多少种选择方法？

（如果两种方案选出来的数不同，或者数相同但顺序不同，就认为是不同的方案）

输入格式

输入第一行为一个整数 $n$，表示有 $n$ 个数。

接下来一行为空格隔开的 $n$ 个正整数，表示这 $n$ 个数。

输出格式

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

样例

3
1 2 3

10

5
1 2 3 4 5

94

样例 1 说明

5 =  1 * 1 + 2 * 2 
7 =  1 * 1 + 2 * 3
13 =  1 * 1 + 2 * 3 + 3 * 2
2 =  1 * 2
13 =  1 * 2 + 2 * 1 + 3 * 3
11 =  1 * 2 + 2 * 3 + 3 * 1
3 =  1 * 3
5 =  1 * 3 + 2 * 1
11 =  1 * 3 + 2 * 1 + 3 * 2
7 =  1 * 3 + 2 * 2

数据范围

对于 $60\%$ 的数据：$1\le n\le 3$；

对于 $100\%$ 的数据：$1\le n \le 9，1\le 每个数 \le 5\times 10^4$