The Number of Good Subsets
You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers.
Return the number of different good subsets in nums modulo 10^9 + 7.
A subset of nums is any array that can be obtained by deleting some (possibly none or all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.
Example 1
Input
nums = [1,2,3,4]Output
6There are 6 good subsets: [1,2], [1,2,3], [1,3], [2], [2,3], and [3].
Example 2
Input
nums = [4,2,3,15]Output
5There are 5 good subsets: [2], [2,3], [2,15], [3], and [15].
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 30