#11083. 好子集的数目

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

给你一个整数数组 a 。如果 a 的一个子集中,所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积,那么我们称它为 好子集 。

比方说,如果 a = [1, 2, 3, 4] :

[2, 3] ,[1, 2, 3] 和 [1, 3] 是 好 子集,乘积分别为 6 = 2 * 3 ,6 = 2 * 3 和 3 = 3 。

[1, 4] 和 [4] 不是 好 子集,因为乘积分别为 4 = 2 * 2 和 4 = 2 * 2 。

请你返回 a 中不同的 好 子集的数目对 10^9 + 7 取余 的结果。

a 中的 子集 是通过删除 a 中一些(可能一个都不删除,也可能全部都删除)元素后剩余元素组成的数组。

如果两个子集删除的下标不同,那么它们被视为不同的子集。

输入格式

第一行:n

第二行:n个整数

输出格式

好 子集的数目对 10^9 + 7 取余 的结果

样例

输入1:

4
1 2 3 4

输出1:

6

解释:好子集为:

  • [1,2]:乘积为 2 ,可以表示为质数 2 的乘积。
  • [1,2,3]:乘积为 6 ,可以表示为互不相同的质数 2 和 3 的乘积。
  • [1,3]:乘积为 3 ,可以表示为质数 3 的乘积。
  • [2]:乘积为 2 ,可以表示为质数 2 的乘积。
  • [2,3]:乘积为 6 ,可以表示为互不相同的质数 2 和 3 的乘积。
  • [3]:乘积为 3 ,可以表示为质数 3 的乘积。

输入2:

4
4 2 3 15

输出2:

5

解释:好子集为:

  • [2]:乘积为 2 ,可以表示为质数 2 的乘积。
  • [2,3]:乘积为 6 ,可以表示为互不相同质数 2 和 3 的乘积。
  • [2,15]:乘积为 30 ,可以表示为互不相同质数 2,3 和 5 的乘积。
  • [3]:乘积为 3 ,可以表示为质数 3 的乘积。
  • [15]:乘积为 15 ,可以表示为互不相同质数 3 和 5 的乘积。

数据范围与提示

1 <= n <= 10^5

1 <= a[i] <= 30