Given an integer array nums, determine the number of non empty square free subsets of nums. Since the result can be very large, return it modulo $10^9 + 7$.

A subset is considered square free if the product of its elements is a square free integer.

A square free integer is an integer that is not divisible by any square number greater than $1$.

A subset of an array is a selection of elements obtained by deleting zero or more elements without changing the order of the remaining elements. Two subsets are considered distinct if they are chosen from different sets of indices.

Constraints:

• $1 \leq$ nums.length $\leq 1000$

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

Input: nums = [2, 3, 5]-List[int]
Output: 7-int
Explanation: Every non-empty subset has a square-free product, resulting in 7 square-free subsets.

Input: nums = [4, 8, 9]-List[int]
Output: 0-int
Explanation: Each element contains a squared prime factor, so no non-empty subset has a square-free product.

Input: nums = [1, 1, 2, 6]-List[int]
Output: 11-int
Explanation: Counting the non-empty subsets whose products remain square-free gives 11 distinct subsets.

Input: nums = [6, 10, 15, 7]-List[int]
Output: 7-int
Explanation: The valid combinations are those whose prime factors do not overlap in a way that creates a square, giving 7 square-free subsets.

Now, 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.