Codeforces Round 448 (Div. 2) |
---|
Закончено |
Как и Вася, Петя опоздал на пару. Преподаватель также дал ему дополнительное задание. Для некоторого массива 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.
Название |
---|