1
class Solution {
2
 public:
3
#define lld long long int
4

5
  int mul(lld a, lld b) {
6
    lld product = (a * b) % MOD;
7
    return product;
8
  }
9

10
  int add(lld a, lld b) {
11
    lld addition = (a + b) % MOD;
12
    return addition;
13
  }
14

15
  const int MOD = 1e9 + 7;
16
  int binary_exponentiation(lld x, int p) {
17
    long long res = 1;
18
    while (p) {
19
      if (p & 1) res = mul(res, x);
20
      x = mul(x, x);
21
      p /= 2;
22
    }
23
    return res;
24
  }
25

26
  int goodSubsets(int pos, int mask, vector<int> &V, vector<vector<int>> &dp, vector<int> &cache) {
27
    if (pos == V.size()) return (mask > 0);
28

29
    if (dp[pos][mask] != -1) return dp[pos][mask] % MOD;
30

31
    if (V[pos] & mask) return dp[pos][mask] = goodSubsets(pos + 1, mask, V, dp, cache) % MOD;
32
    return dp[pos][mask] =
33
               add(mul(cache[V[pos]], goodSubsets(pos + 1, mask | V[pos], V, dp, cache)),
34
                   goodSubsets(pos + 1, mask, V, dp, cache));
35
  }
36

37
  int numberOfGoodSubsets(vector<int> &nums) {
38
    int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
39

40
    vector<int> V;
41
    vector<int> cache(1025, 0);
42

43
    int ones = 0;
44

45
    for (auto x : nums) {
46
      int num = 0, k = 0;
47
      int flag = 1;
48

49
      for (auto j : primes) {
50
        int cnt = 0;
51
        while (x % j == 0) {
52
          x /= j;
53
          cnt++;
54
          if (cnt > 1) break;
55
        }
56

57
        if (cnt > 1) {
58
          flag = 0;
59
          break;
60
        }
61

62
        if (cnt == 1) num = num | (1 << k);
63

64
        ++k;
65
      }
66

67
      if (flag == 0) continue;
68

69
      if (num == 0) {
70
        ones++;
71
        continue;
72
      }
73

74
      cache[num]++;
75
      if (cache[num] > 1) continue;
76

77
      V.push_back(num);
78
    }
79

80
    vector<vector<int>> dp(V.size(), vector<int>(1024, -1));
81

82
    int ans = goodSubsets(0, 0, V, dp, cache);
83
    ans = mul(binary_exponentiation(2, ones), ans);
84

85
    return ans;
86
  }
87
};