CF895C.Square Subsets

Petya was late for the lesson too. The teacher gave him an additional task. For some array a Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.

Two ways are considered different if sets of indexes of elements chosen by these ways are different.

Since the answer can be very large, you should find the answer modulo 109 + 7.

佩佳又上课迟到了。老师给他布置了一道附加题：对于某个数组 $a$，佩佳需要找出从中选取非空子集（即至少包含一个元素）的方法数，使得该子集中所有元素的乘积等于某个整数的平方。

如果两种选取方式所选元素的下标集合不同，则认为这两种方式是不同的。

由于答案可能非常大，请将答案对 $10^9 + 7$ 取模后输出。

First line contains one integer n (1 ≤ n ≤ 105) — the number of elements in the array.

Second line contains n integers a__i (1 ≤ a__i ≤ 70) — the elements of the array.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 数组中元素的个数。

第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 70$）—— 数组的元素。

Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109 + 7.

输出一个整数——表示选择若干元素，使得它们的乘积模 $10^9 + 7$ 意义下为某个整数的平方的不同方案数。

In first sample product of elements chosen by any way is 1 and 1 = 12. So the answer is 24 - 1 = 15.

In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.

在第一个样例中，以任意方式选择的元素的乘积均为 $1$，且 $1 = 1^2$。因此答案为 $2^4 - 1 = 15$。

在第二个样例中，共有六种不同的方式选择元素，使其乘积为 $4$；仅有一种方式使其乘积为 $16$。因此答案为 $6 + 1 = 7$。