Shared code

import sys
import os
from math import log2, ceil
MOD = 10 ** 9 + 7


def inplist():
    return [int(i) for i in input().split()]


def pow(a, b, mod):
    x = 1
    while b:
        if b & 1:
            x = (x * a) % mod
        a = (a * a) % mod
        b >>= 1
    return x


def debug(**kwargs):
    st = [f"{name}: {val}" for (name, val) in kwargs.items()]
    print(*st, sep=" | ")


dp = [[0] * 5000 ** 2 for _ in range(2)]


def sieve(n):
    if n < 2:
        return []

    # Create a boolean array "is_prime[0..n]" and initialize
    # all entries it as true.
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for p in range(2, int(n ** 0.5) + 1):
        # If is_prime[p] is not changed, then it is a prime
        if is_prime[p]:
            # Update all multiples of p starting from p*p
            # (multiples smaller than p*p have already been marked)
            for i in range(p * p, n + 1, p):
                is_prime[i] = False

    # Return list of primes
    return [p for p, prime in enumerate(is_prime) if prime]


primes = sieve(5000)


def subsetcount(arr):
    if not arr: return 1
    n = ceil(log2(5000))
    oldState = [0] * (1 << n)
    newState = [0] * (1 << n)
    oldState[0] = 1
    for a in arr:
        for j in range(1 << n):
            newState[j] = (oldState[j] + oldState[j ^ a]) % MOD
        oldState = newState[::]
    return newState[0]


def solve():
    n = int(input())
    arr = inplist()
    ones = arr.count(1)
    arr = [x for x in arr if x != 1]
    arrmapped = []
    for x in arr:
        curr = 0
        for p in primes:
            while x % p == 0:
                curr ^= p
                x //= p
            if x == 1: break
        arrmapped.append(curr)
    ones += arrmapped.count(0)
    arrmapped = [x for x in arrmapped if x != 0]
    sqpr = pow(2, ones, MOD)
    return (sqpr * subsetcount(arrmapped)) % MOD


def main():
    t = 1
    # t=int(input())
    for _ in range(t):
        print(solve())


if __name__ == "__main__":
    main()