시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB382186844617.518%

문제

다솜이는 슈퍼에서 사탕을 사려고 한다. 슈퍼에는 사탕이 N종류가 있다. 각각의 사탕은 가격이 있다. 다솜이는 사탕을 사는데, 사탕의 가격의 합이 소수가 되게하려고 한다.

가격이 같은 사탕은 모양이 같게 생겼다. 따라서 다솜이는 사탕을 적절히 샀을 때, 그 모양이 전부 똑같은 방법은 사지 않으려고 한다.

예를 들어, (1, 2, 1, 3, 1)을 사는 것과, (3, 1, 1, 1, 2)를 사는 것은 같은 방법이다. 따라서 한번만 세야 한다.

입력

첫째 줄에 슈퍼에 있는 사탕의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사탕의 가격이 주어진다. 사탕의 가격은 10,000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 다솜이가 사탕을 살 수 있는 방법의 경우의 수를 출력한다.

예제 입력 1

4
1
1
2
7

예제 출력 1

5

예제 입력 2

10
1
1
1
1
1
1
1
1
1
1

예제 출력 2

4

예제 입력 3

6
4
6
8
10
12
14

예제 출력 3

0

예제 입력 4

8
1
2
4
8
16
32
64
128

예제 출력 4

54

예제 입력 5

10
1234
5678
9012
3456
7890
2345
6789
123
4567
8901

예제 출력 5

97

예제 입력 6

3
0
0
7

예제 출력 6

3

출처