using u64 = unsigned long long;
class Solution {
public:
    const int MOD = int(1e9) + 7;
    u64 go(int idx, int pf_state, vector<int>& nums, array<u64, 2000>& pf_nums, array<array<u64, 1050>, 1050>& memo) {
        if (idx == nums.size()) return 0;
        if (memo[idx][pf_state] != -1) return memo[idx][pf_state];

        u64 out = 0;
        if ((pf_state & pf_nums[idx]) == 0) {
            auto without = go(idx + 1, pf_state, nums, pf_nums, memo);
            auto with = go(idx + 1, pf_state | pf_nums[idx], nums, pf_nums, memo);
            out = out + without;
            out %= MOD;
            out = (out + with + 1) % MOD;
        } else {
            out = go(idx + 1, pf_state, nums, pf_nums, memo);
        }
        memo[idx][pf_state] = out;
        return out;
    }
    int squareFreeSubsets(vector<int>& A) {
        array<u64, 2000> pf_nums = {};
        vector<int> nums{};
        nums.reserve(A.size());
        for (auto num : A) {
            if (num == 4 || num == 8 || num == 9 || num == 12 || num == 16) continue;
            if (num == 18 || num == 20 || num == 24 || num == 25 || num == 27) continue;
            if (num == 28) continue;

            nums.push_back(num);
        }
        const vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

        for (auto idx = 0; idx < nums.size(); idx++) {
            auto num = nums[idx];
            int state = 0;
            for (auto prime_idx = 0; prime_idx < primes.size(); prime_idx++) {
                auto prime = primes[prime_idx];
                while (num % prime == 0) {
                   num /= prime;
                   state |= (1 << prime_idx);
                }
            }
            pf_nums[idx] = state;
        }


        array<array<u64, 1050>, 1050> memo = {};
        for (auto i = 0; i < 1050; i++) {
            for (auto j = 0; j < 1050; j++) {
                memo[i][j] = -1;
            }
        }
        return go(0, 0, nums, pf_nums, memo);
    }
};