Untitled

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod =1e9+7;

vector<int>prime = {2,3,5,7,11,13,17,19,23,29};
map<int,vector<int>>mp;

  bool check(int n){
    if(n%4==0 || n%9==0 || n%16==0 || n%25==0) return false;
    return true;
  }
  int solve(int ind,int mask,vector<int>&a,vector<vector<int>>&dp){
    if(ind==a.size()){
      return mask!=0;
    }
    
    if(dp[ind][mask]!=-1) return dp[ind][mask];
    
    int ans=solve(ind+1,mask,a,dp)%mod;
    
    int temp=mask;
    bool flag=true;
    
    for(auto it:mp[a[ind]]){
      if(mask&(1<<it)) {
        flag=false;
        break;
      }
      else{
        temp |=(1<<it);
      }
    }
  
    if(flag) ans=(ans+solve(ind+1,temp,a,dp))%mod;
    
    return dp[ind][mask]=ans;
  }
  int main() {

     int n;cin>>n;
     vector<int>a;
     for(int i=0;i<n;i++){
       int x;cin>>x;
       if(check(x)) a.push_back(x);
     }
     vector<vector<int>> dp(n,vector<int>(1<<11,-1));

     for(int i=2;i<31;i++){
       for(int j=0;j<10;j++){
         if(i%prime[j]==0) mp[i].push_back(j);
       }
     }
     cout<<solve(0,0,a,dp)<<endl;
    return 0;

  }