Candy

Time limit2sMemory limit128 MB

Summary

Given candy prices, count the distinct ways to pick a multiset of candies whose price sum is a prime number.

Level: Medium6 of 10
Topics: Dynamic programming, Number theory, Combinatorics, Math
Solved: No attempts yet

Problem

Dasom wants to buy candy at a store. The store has N candies, and each candy has one price. She wants to choose candies so that the sum of their prices is a prime number.

Candies with the same price are considered to have the same shape. Therefore, if the number of candies chosen from each price is the same, selections that differ only in order are counted once.

For instance, choosing (1, 2, 1, 3, 1) and choosing (3, 1, 1, 1, 2) are the same method.

Input

The first line contains N, the number of candies in the store. N is a positive integer not greater than 50. Each of the next N lines contains the price of one candy. Every price is a nonnegative integer not greater than 10,000.

Output

Print the number of ways Dasom can buy candies.

Examples6

Example 1
Input
```
4
1
1
2
7
```
Expected output
```
5
```
Example 2
Input
```
10
1
1
1
1
1
1
1
1
1
1
```
Expected output
```
4
```
Example 3
Input
```
6
4
6
8
10
12
14
```
Expected output
```
0
```
Example 4
Input
```
8
1
2
4
8
16
32
64
128
```
Expected output
```
54
```

Example 5

Input

Expected output

Example 6
Input
```
3
0
0
7
```
Expected output
```
3
```