Candy

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.

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.

Print the number of ways Dasom can buy candies.