Petya 上课也迟到了。老师给了他一项额外的任务。对于某些数组,Petya 应该找到多种不同的方法来从中选择元素的非空子集,使得它们的乘积等于某个整数的平方。
如果两种方式选择的元素索引集不同,则认为两种方式不同。
由于答案可能非常大,因此您应该以 109 + 7 为模求出答案。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 数组中的元素数量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 70) — 数组的元素。
输出
打印一个整数——选择某些元素的不同方式的数量,以便它们的乘积是某个整数模 109 + 7 的平方。
示例
输入 #1
4 1 1 1 1
输出 #1
15
输入 #2
4 2 2 2 2
输出 #2
7
输入 #3
5 1 2 4 5 8
输出 #3
7
注意
在第一个示例中,以任何方式选择的元素的乘积都是 1 并且 1 = 12。所以答案是 24 - 1 = 15。
在第二个示例中,有六种不同的方法来选择元素,使其乘积为 4,只有一种方法可以使其乘积为 16。所以答案是 6 + 1 = 7。