1
from collections import Counter
2
from functools import lru_cache
3
from typing import List, Tuple
4

5
PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
6

7
BIG_NUMBER = 10**9 + 7
8

9

10
@lru_cache(maxsize=32)
11
def factor(n) -> Tuple[int, bool]:
12
    """
13
    :param n: 1 < n <= max(PRIMES)
14
    :return: (factors in bit mask, has duplicate primes)
15
    """
16
    output = 0
17

18
    for e in PRIMES:
19
        while n > 1 and n % e == 0:
20
            mask = 1 << e
21

22
            if mask & output:
23
                return -1, False
24

25
            output |= mask
26

27
            n //= e
28

29
        if n == 1:
30
            break
31

32
    return output, True
33

34

35
class Solution:
36
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
37
        masks = []
38

39
        for e in nums:
40
            if 1 < e and (fr := factor(e))[1]:
41
                masks.append(fr[0])
42

43
        cnt = Counter(masks)
44
        good_nums = Counter({0: 0})
45

46
        for mask in cnt:
47
            for f in tuple(good_nums):
48
                if f & mask:  # some prime dividing "mask" is also dividing the "f"
49
                    continue
50

51
                new_mask = f | mask
52

53
                count_for_new_mask = good_nums[new_mask] + cnt[mask] * (
54
                    good_nums[f] or 1
55
                )
56

57
                good_nums[new_mask] = count_for_new_mask % BIG_NUMBER
58

59
        effect_of_one = pow(2, nums.count(1), BIG_NUMBER)
60
        total_subsets_without_one = sum(good_nums.values()) % BIG_NUMBER
61

62
        return (effect_of_one * total_subsets_without_one) % BIG_NUMBER