問題
어떤 상자 안에 n개의 원소가 들어 있다. 각각의 원소는 0 이상의 정수이다. 배낭 안에 들어있는 원소의 순서는 중요하지 않다. A에서 0개 이상의 원소를 제거해서 B를 만들 수 있는 경우, "A는 B의 부분 배낭"이라고 한다. 또한 배낭의 무게는 배낭에 들어있는 원소들의 합을 의미한다.
예를 들어 (1, 2, 1, 3, 1)인 배낭과 (3, 1, 1, 1, 2)인 배낭은 같은 상태이다. 하지만 (1, 2, 3, 3)인 배낭은 다르다. (1, 2)와 (3, 1, 1)은 (1, 2, 1, 3, 1)의 부분 배낭이지만, (1, 2, 2)는 부분 배낭이 아니다.
만약 배낭에 들어가 있는 원소가 (1, 2, 1, 3, 1)와 같이 주어졌을 때, 이 배낭의 총 무게의 합은 8이다. 배낭의 정보가 주어졌을 때 무게의 합이 소수(prime-number)인 가능한 부분 배낭의 경우의 수를 구하시오.
入力
첫 번째 줄에는 배낭의 원소의 개수 N(N≤50)이 주어지며 그 다음 줄에는 N개의 원소들의 무게가 주어진다.
원소들의 무게는 0 이상 10,000 이하이다.
出力
주어진 배낭에 대해서 만들어 질 수 있는 부분 배낭의 가지수를 출력한다.
例題
4
1 1 2 7
5
出典
Online Contest
ログインしないとコードを書けません。