UOJ Logo LFYZ Online Judge

LFYZOJ

#342. 【2018 国庆雅礼 NOIP 培训】D4T1 x

统计

问题背景

$\dfrac 1 4$ 遇到了一道水题,叒完全不会做,于是去请教小 D。小 D 都没看就切掉了这题,嘲讽了 $\dfrac 1 4$ 一番就离开了。

于是,$\dfrac 1 4$ 只好来问你,这道题是这样的:

问题描述

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

将 $\{1, 2, \cdots, n\}$ 划分成两个非空集合 $S,T$,使得 $\gcd(\prod\limits_{i\in S}a_i,\prod\limits_{i\in T}a_i)=1$。

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

输入格式

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

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

第二行,$n$ 个正整数,代表 {ai}。

输出格式

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

样例

Input

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

Output

6
0
2

Explanation

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

子任务

保证,$0 ≤ t ≤ 5,1 ≤ n ≤ 105,1 ≤ ai ≤ 106$。

Subtask    分值    $n\le$    $a_i \le$    
1201515
23010001000000
3101000001
4102
5301000000

时限 1s,空限 512M

来源

2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。