시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 262 40 34 15.315%

문제

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

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

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

입력

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

출력

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

예제 입력

4
1
1
2
7

예제 출력

5

힌트

출처