총 N개의 양의 정수로 이루어진 수열 B = B₀, ..., B_N-1가 주어진다. 이때, 아래와 같은 성질을 만족하는 수열 A = A₀, ..., A_N-1을 만들려고 한다.</p>

• 수열 A의 모든 수는 서로 달라야 한다.
• 모든 A_i는 1보다 커야 한다.
• 모든 i에 대해서, A_i^B_i (A_i의 B_i제곱)은 P_i로 나누어 떨어져야 한다. 이때, P_i는 A에서 A_i를 제외한 수를 모두 곱한 값이다. 즉, P_i = A₀×A₁×...×A_i-1×A_i+1×...×A_N-1 이다.

수열 A를 만들 수 있는지 없는지 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 수열의 크기 N (2 ≤ N ≤ 50)이 주어진다. 둘째 줄에는 수열 B가 주어진다. (1 ≤ B_i ≤ 10)

출력 형식

첫째 줄에 수열 A를 만들 수 있으면 1을 없으면 0을 출력한다.

예제 입력 1

2
2 1

예제 출력 1

1

예제 입력 2

2
1 1

예제 출력 2

0

예제 입력 3

3
7 7 7

예제 출력 3

1