Как и Вася, Петя опоздал на пару. Преподаватель также дал ему дополнительное задание. Для некоторого массива a необходимо вычислить количество различных способов выбрать некоторое непустое подмножество его элементов так, чтобы их произведение было равно квадрату некоторого натурального числа.
Два способа считаются различными если различаются множества индексов элементов, выбранных в первом и во втором способах.
Так как ответ может быть очень большим, необходимо вычислить лишь остаток от деления ответа на 109 + 7.
Выходные данные
Выведите одно целое число — остаток от деления искомого количества способов на 109 + 7.
Примечание
В первом тесте произведение чисел выбираемых любым возможным способом равно 1. Так как 1 = 12, ответ равен 24 - 1 = 15.
Во втором тесте можно получить произведение равное 16 одним способом и произведение равное 4 шестью способами. Поэтому ответ равен 6 + 1 = 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1 1 1
|
15
|
|
2
|
4
2 2 2 2
|
7
|
|
3
|
5
1 2 4 5 8
|
7
|