C. Квадратные подмножества
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как и Вася, Петя опоздал на пару. Преподаватель также дал ему дополнительное задание. Для некоторого массива a необходимо вычислить количество различных способов выбрать некоторое непустое подмножество его элементов так, чтобы их произведение было равно квадрату некоторого натурального числа.

Два способа считаются различными если различаются множества индексов элементов, выбранных в первом и во втором способах.

Так как ответ может быть очень большим, необходимо вычислить лишь остаток от деления ответа на 109 + 7.

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — размер массива.

Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 70) — элементы массива.

Выходные данные

Выведите одно целое число — остаток от деления искомого количества способов на 109 + 7.

Примеры
Входные данные
4
1 1 1 1
Выходные данные
15
Входные данные
4
2 2 2 2
Выходные данные
7
Входные данные
5
1 2 4 5 8
Выходные данные
7
Примечание

В первом тесте произведение чисел выбираемых любым возможным способом равно 1. Так как 1 = 12, ответ равен 24 - 1 = 15.

Во втором тесте можно получить произведение равное 16 одним способом и произведение равное 4 шестью способами. Поэтому ответ равен 6 + 1 = 7.