x

x.cpp/in/out

• 时间限制：1.0s
• 空间限制：512MB

题目描述

给定一个长度为 $n$ 的正整数序列 $\{a_i\}$。

将 $\{1, 2, \ldots, n\}$ 划分成两个非空集合 $S$、$T$，使得 $\gcd\left(\prod_{i \in S} a_i, \prod_{i \in T} a_i\right) = 1$。

求划分方案数，对 $10^9 + 7$ 取模。

输入格式

从文件 x.in 中读入数据。

第一行，一个非负整数 $t$，代表数据组数。

每组数据的第一行，一个正整数 $n$。

第二行，$n$ 个正整数，代表 $\{a_i\}$。

输出格式

输出到文件 x.out 中。

输出 $t$ 行，每行一个非负整数，代表答案对 $10^9 + 7$ 取模的结果。

样例输入

3
3
2 3 1
3
2 3 6
4
2 3 6 1

样例输出

6
0
2

样例解释

• 第 1 组数据，任意一种非空集合划分均满足。
• 第 2 组数据，任意一种非空集合划分均不满足。
• 第 3 组数据，$S = \{1, 2, 3\}, T = \{4\}$，$\gcd(a_1 \cdot a_2 \cdot a_3, a_4) = 1$；或者 $S = \{4\}, T = \{1, 2, 3\}$，$\gcd(a_4, a_1 \cdot a_2 \cdot a_3) = 1$。

数据范围

保证 $0 \le t \le 5$，$1 \le n \le 10^5$，$1 \le a_i \le 10^6$。