Square Subsets

Petya도 수업에 늦었다. 선생님은 그에게 추가 과제를 주었다. 어떤 배열 a에 대해 Petya는 원소들의 곱이 어떤 정수의 제곱과 같도록 원소의 공집합이 아닌 부분집합을 선택하는 서로 다른 방법의 수를 구해야 한다.

두 방법으로 선택한 원소들의 인덱스 집합이 서로 다르면, 두 방법은 서로 다른 것으로 간주한다.

답이 매우 클 수 있으므로, 답을 109 + 7로 나눈 나머지를 구해야 한다.

첫 번째 줄에는 정수 하나 n (1 ≤ n ≤ 105) — 배열의 원소 수가 주어진다.

두 번째 줄에는 n개의 정수 ai (1 ≤ ai ≤ 70) — 배열의 원소들이 주어진다.

선택한 원소들의 곱이 어떤 정수의 제곱이 되도록 일부 원소를 선택하는 서로 다른 방법의 수를 109 + 7로 나눈 나머지를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 어떤 방법으로 원소를 선택하더라도 선택한 원소들의 곱은 1이고, 1 = 12이다. 따라서 답은 24 - 1 = 15이다.

두 번째 예제에서는 원소들의 곱이 4가 되도록 선택하는 서로 다른 방법이 여섯 가지이고, 원소들의 곱이 16이 되도록 선택하는 방법은 하나뿐이다. 따라서 답은 6 + 1 = 7이다.