The Number of Good Subsets

Challenge Points: 30

Level: Hard

You are given an integer array nums. A subset of this array is considered good if the product of all its elements can be expressed as the multiplication of distinct prime numbers only (no prime is allowed to repeat in the factorization).

For example, if the subset’s product is 30 = 2 × 3 × 5, then it is valid because each prime appears once.
But a product like 12 = 2 × 2 × 3 is not valid, as the prime 2 repeats.

You must return the total number of good subsets that can be formed from nums.
The answer must be returned modulo 10⁹ + 7.

A subset is formed by choosing any combination of elements (possibly deleting none or all), and two subsets are considered different if their chosen indices differ.

Example 1:

Input: nums = [1, 2, 3, 4]

Output: 6

Explanation:

Valid good subsets include: [2] → product = 2 [3] → product = 3 [2,3] → product = 6 [1,2] [1,3] [1,2,3] 4 is not usable because its prime factor 2 repeats (4 = 2 × 2).