#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e5+;

const int MOD=1e9+;

int a[N];

int cnt[];

int dp[][(<<)+];

int s[];

int prime[]={,,,,,,,,,,,,,,,,,,};

int _2p[N];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    for(int i=;i<=;i++)

    {

        int t=i;

        for(int j=;j<;j++)

        {

            while(t%prime[j]==)t/=prime[j],s[i]^=(<<j);

        }

    }

    _2p[]=;

    for(int i=;i<N;i++)_2p[i]=(_2p[i-]*)%MOD;

    int n;

    cin>>n;

    for(int i=;i<=n;i++)cin>>a[i],cnt[a[i]]++;

    dp[][]=;

    for(int i=;i<=;i++)

    {

        if(!cnt[i])

        {

            for(int j=;j<(<<);j++)

            dp[i][j]=dp[i-][j];

        }

        else

        {

            for(int j=;j<(<<);j++)

            {

                dp[i][j^s[i]]=((ll)dp[i][j^s[i]]+(ll)_2p[cnt[i]-]*dp[i-][j])%MOD;//从cnt[i]个数个选奇数个，C(n，1)+C(n,3)+...=2^(n-1)

                dp[i][j]=((ll)dp[i][j]+(ll)_2p[cnt[i]-]*dp[i-][j])%MOD;//从cnt[i]个数个选偶数个,C(n,0)+C(n,2)*C(n,4)+...=2^(n-1)

            }

        }

    }

    cout<<(dp[][]-)%MOD<<endl;//减去0的情况

return ; }