1
class Solution {
2
  static int MOD = 1_000_000_000 + 7;
3

4
  // These numbers contain duplicate factors (e.g 4, 8, 9, 25), will be excluded
5
  static List<Integer> excludes = new ArrayList<>();
6

7
  // Distinct prime factors of composites
8
  // e.g 6 = 2 * 3, 15 = 3 * 5, 30 = 2 * 3 * 5
9
  static List<Integer>[] factors = new List[31];
10

11
  // Coprime numbers permutation
12
  // Coprime means some composites don't have common factor and can coexist
13
  // e.g. 14 = 2 * 7 and 15 = 3 * 5
14
  static List<int[]> coprimes_pmt = new ArrayList<>();
15

16
  static {
17
    List<Integer> primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29);
18
    int[] masks = new int[31];
19

20
    for (int i = 4; i <= 30; i++) {
21
      // exclude 4, 8, 9, 25 ...
22
      if (i % 4 == 0 || i % 9 == 0 || i % 25 == 0) {
23
        excludes.add(i);
24
        continue;
25
      }
26

27
      if (primes.contains(i)) {
28
        continue;
29
      }
30

31
      // Set distinct prime factors of composites
32
      for (int j = 0; j < primes.size(); j++) {
33
        if (i % primes.get(j) == 0) {
34
          if (factors[i] == null) {
35
            factors[i] = new ArrayList<>();
36
          }
37
          factors[i].add(primes.get(j));
38
          masks[i] |= (1 << j);
39
        }
40
      }
41
    }
42

43
    // Recursively build coprime permutation
44
    buildCoprimes(0, masks, 0, new int[] {});
45
  }
46

47
  static void buildCoprimes(int mask, int[] masks, int num, int[] prev) {
48
    for (; num < masks.length; num++) {
49
      if (masks[num] > 0 && (mask & masks[num]) == 0) {
50
        int[] arr = Arrays.copyOf(prev, prev.length + 1);
51
        arr[prev.length] = num;
52
        coprimes_pmt.add(arr);
53
        buildCoprimes(mask | masks[num], masks, num + 1, arr);
54
      }
55
    }
56
  }
57

58
  public int numberOfGoodSubsets(int[] nums) {
59

60
    int[] prime_count = new int[31];
61
    int[] composite_count = new int[31];
62

63
    for (int num : nums) {
64
      prime_count[num]++;
65
    }
66

67
    // exclude numbers having duplicate factors, like 4, 8, 9, 25...
68
    for (int ex : excludes) {
69
      prime_count[ex] = 0;
70
    }
71

72
    // split prime numbers and composite numbers
73
    for (int i = 0; i < prime_count.length; i++) {
74
      if (factors[i] != null) {
75
        composite_count[i] = prime_count[i];
76
        prime_count[i] = 0;
77
      }
78
    }
79

80
    // sum result for prime numbers
81
    long result = sum(prime_count, null);
82

83
    // sum result for coprime numbers
84
    for (int[] coprimes : coprimes_pmt) {
85
      long count_mul = 1;
86
      for (int composite : coprimes) {
87
        count_mul *= composite_count[composite];
88
      }
89

90
      if (count_mul > 0) {
91
        result = (result + (sum(prime_count, coprimes) + 1) * count_mul) % MOD;
92
      }
93
    }
94

95
    // Each `1` will double the result
96
    while (prime_count[1] > 0) {
97
      result = (result * 2) % MOD;
98
      prime_count[1]--;
99
    }
100

101
    return (int) result;
102
  }
103

104
  int sum(int[] prime_count, int[] coprimes) {
105
    int[] dp = Arrays.copyOf(prime_count, prime_count.length);
106

107
    // Exclude prime factors of coprime numbers
108
    if (coprimes != null) {
109
      for (int composite : coprimes) {
110
        for (int factor : factors[composite]) {
111
          dp[factor] = 0;
112
        }
113
      }
114
    }
115

116
    for (int i = 3; i <= 29; i++) {
117
      dp[i] = (int) ((dp[i - 1] + 1L * dp[i - 1] * dp[i] + dp[i]) % MOD);
118
    }
119
    return dp[29];
120
  }
121
}