该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

给一个数组，$a_i\le 70$，选一个子集使得乘积为平方数，求方案数？

题目描述

奆上课也迟到了。老师给他布置了额外的任务。

对于一个数组，奆需要找出有多少种不同的方法可以从中选择非空的元素子集，使它们的乘积等于某个整数的平方。

由于答案可能非常大，你应该求出答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行输入一个整数 $n ( 1 \le n \le 10^5 )$ ,表示数组中元素的个数。

第二行包含 $n$ 个整数 $a_i ( 1 \le a_i \le 70 )$ ，表示数组中的元素。

输出格式

输出一个整数，即答案对 $10^9 + 7$ 取模后的结果。

输入输出样例 #1

输入 #1

4
1 1 1 1

输出 #1

15

输入输出样例 #2

输入 #2

5
1 2 4 5 8

输出 #2

7