<p>You are given an integer array <code>nums</code>. We call a subset of <code>nums</code> <strong>good</strong> if its product can be represented as a product of one or more <strong>distinct prime</strong> numbers.</p>

<ul>
	<li>For example, if <code>nums = [1, 2, 3, 4]</code>:

	<ul>
		<li><code>[2, 3]</code>, <code>[1, 2, 3]</code>, and <code>[1, 3]</code> are <strong>good</strong> subsets with products <code>6 = 2*3</code>, <code>6 = 2*3</code>, and <code>3 = 3</code> respectively.</li>
		<li><code>[1, 4]</code> and <code>[4]</code> are not <strong>good</strong> subsets with products <code>4 = 2*2</code> and <code>4 = 2*2</code> respectively.</li>
	</ul>
	</li>
</ul>

<p>Return <em>the number of different <strong>good</strong> subsets in </em><code>nums</code><em> <strong>modulo</strong> </em><code>10<sup>9</sup> + 7</code>.</p>

<p>A <strong>subset</strong> of <code>nums</code> is any array that can be obtained by deleting some (possibly none or all) elements from <code>nums</code>. Two subsets are different if and only if the chosen indices to delete are different.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The good subsets are:
- [1,2]: product is 2, which is the product of distinct prime 2.
- [1,2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [1,3]: product is 3, which is the product of distinct prime 3.
- [2]: product is 2, which is the product of distinct prime 2.
- [2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [3]: product is 3, which is the product of distinct prime 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,2,3,15]
<strong>Output:</strong> 5
<strong>Explanation:</strong> The good subsets are:
- [2]: product is 2, which is the product of distinct prime 2.
- [2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [2,15]: product is 30, which is the product of distinct primes 2, 3, and 5.
- [3]: product is 3, which is the product of distinct prime 3.
- [15]: product is 15, which is the product of distinct primes 3 and 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 30</code></li>
</ul>

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        N, res, mod = 30, 0, 10 ** 9 + 7

        cnt = [0] * (N + 1)
        for v in nums: cnt[v] += 1
       
        # 2,3,5,7,11,13,17,19,23,29
        primes = [
            0b0000000000, # 0
            0b0000000000, # 1
            0b0000000001, # 2
            0b0000000010, # 3
            0b0000000000, # 4
            0b0000000100, # 5
            0b0000000011, # 6
            0b0000001000, # 7
            0b0000000000, # 8
            0b0000000000, # 9
            0b0000000101, # 10
            0b0000010000, # 11
            0b0000000000, # 12
            0b0000100000, # 13
            0b0000001001, # 14
            0b0000000110, # 15
            0b0000000000, # 16
            0b0001000000, # 17
            0b0000000000, # 18
            0b0010000000, # 19
            0b0000000000, # 20
            0b0000001010, # 21
            0b0000010001, # 22
            0b0100000000, # 23
            0b0000000000, # 24
            0b0000000000, # 25
            0b0000100001, # 26
            0b0000000000, # 27
            0b0000000000, # 28
            0b1000000000, # 29
            0b0000000111 # 30
        ]

        # dp = [[-1] * (1 << 10) for _ in range(N + 1)]

        # def dfs(i, s):
        #     ans = 0
        #     if i == 1:
        #         if s == 0:
        #             ans = 1
        #             for j in range(cnt[1]):
        #                 ans = (ans << 1) % mod
        #         return ans
            
        #     if dp[i][s] != -1: return dp[i][s]

        #     ans = (ans + dfs(i - 1, s)) % mod
        #     if primes[i] != 0 and cnt[i] != 0 and ((s & primes[i]) == primes[i]):
        #         ans = (ans + dfs(i - 1, s ^ primes[i]) * cnt[i]) % mod

        #     dp[i][s] = ans
        #     return ans

        cnt1 = 1
        for j in range(cnt[1]):
            cnt1 = (cnt1 << 1) % mod
        
        dp = [0] * (1 << 10)
        dp[0] = cnt1

        for i in range(2, N + 1):
            for s in range((1 << 10) - 1, 0, -1):
                if primes[i] != 0 and cnt[i] != 0 and ((s & primes[i]) == primes[i]):
                    dp[s] = (dp[s] + dp[s ^ primes[i]] * cnt[i]) % mod

        res = 0
        for s in range(1, 1 << 10):
            res = (res + dp[s]) % mod

        return res

1542