For a given integer array, nums, you can say that a subset of nums is called “good” if the product of its elements can be expressed as a product of one or more distinct prime numbers, i.e., no prime factor appears more than once.

For example, if nums $= [1, 2, 5, 6]$, then:

• $[2, 5]$, $[1, 2, 5]$, and $[6]$ are good subsets with products $2 \times 5 = 10$, $1 \times 2 \times 5 = 10$, and $2 \times 3 = 6$, respectively.

• $[2, 6]$ and $[1, 2, 6]$ are not good subsets as their products are $2 \times 2 \times 3 = 12$, which repeats a prime factor.

Your task is to return the number of different good subsets in nums modulo $10^9 + 7$.

A subset is formed by deleting zero or more elements from nums. Two subsets are considered different if they are formed by deleting different indexes.

Constraints:

• $1 \leq$ nums.length $\leq 10^5$

• $1 \leq$ nums[i] $\leq 30$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.