Проверка партий на складе
(Время: 0,25 сек. Память: 32 Мб Сложность: 81%)
На складе компании проводят быструю проверку качества упаковки. Каждая партия товара описывается набором меток, и каждая метка соответствует одному из заранее утверждённых типов компонентов (их не больше 50). Для удобства учёта партия кодируется натуральным числом: в разложении этого числа на простые множители используются только простые из утверждённого набора. При этом степень простого множителя отражает, сколько раз соответствующий компонент «участвовал» при формировании партии. Инженер по контролю качества считает, что выбранная группа партий «идеально сбалансирована», если при перемножении кодов этих партий получается число, у которого для каждого компонента суммарное число участий – чётное. То есть итоговый продукт «симметричен по компонентам».
Вам нужно автоматизировать проверку. Для каждого тестового случая дано N натуральных чисел a1 … an, каждое из которых раскладывается только по простым множителям из фиксированного набора (размер набора ≤ 50). Найдите, сколькими различными способами можно выбрать непустое подмножество данных чисел так, чтобы произведение выбранных чисел было полностью «сбалансированным», то есть все степени простых множителей в произведении были чётными. Так как ответ может быть большим, выведите его по модулю 109 + 7.
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число Q – количество тестовых случаев. В каждом наборе содержится одно натуральное число N, далее N чисел ai через пробел. (1 ≤ Q ≤ 100; 1 ≤ N ≤ 104; 1 ≤ ai ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите Q чисел по одному в каждой строке.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
4
24 6 8 2
3
3 9 27
2
2 6 | 3
3
0 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
