#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int c=16;
int ct[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll dp[1<<16][2][2];
const ll M=998244353;
void solve() {
    int n;
    cin>>n;
    vector<pair<int,int>> a(n);
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        a[i].second=x;
        for(int j=0;j<c;j++){
            while(x%ct[j]==0)   x/=ct[j];
        }
        if(x!=1)    a[i].first=x;
    }
    sort(a.begin(),a.end());
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++){
        auto [u,x]=a[i-1];
        if(a[i-1].first==0||(i!=1&&a[i-1].first!=a[i-2].first)){
            for(int j=0;j<(1<<c);j++){
                dp[j][i&1][0]=dp[j][(i-1)&1][0]+dp[j][(i-1)&1][1];
                dp[j][i&1][1]=0;
            }
            auto dfs=[&](auto self,int j,int dep,int gx,int nxt)->void {
                if(dep==c)  {
                    dp[j|nxt][i&1][1]=(dp[j|nxt][i&1][1]+(dp[j][(i-1)&1][0]+dp[j][(i-1)&1][1])%M*((u==0?gx:gx/u*(u-1))%M)%M)%M;
                    return ;
                }
                self(self,j|(1<<dep),dep+1,gx,nxt);
                if(x%ct[dep]==0)    {
                    nxt|=(1<<dep);
                    gx=gx/ct[dep]*(ct[dep]-1);
                }
                self(self,j,dep+1,gx,nxt);
            };
            dfs(dfs,0,0,x,0);
            // if(i==2)    cerr<<dp[1][0][1]<<' '<<dp[1][0][0]<<'\n';
        }
        else{
            for(int j=0;j<(1<<c);j++){
                dp[j][i&1][0]=dp[j][(i-1)&1][0];
                dp[j][i&1][1]=dp[j][(i-1)&1][1];
            }
            auto dfs=[&](auto self,int j,int dep,int gx,int nxt)->void {
                if(dep==c)  {dp[j|nxt][i&1][1]=(dp[j|nxt][i&1][1]+dp[j][(i-1)&1][0]*((u==0?gx:gx/u*(u-1))%M+dp[j][(i-1)&1][1]*gx%M)%M)%M;return ;}
                self(self,j|(1<<dep),dep+1,gx,nxt);
                if(x%ct[dep]==0)    {
                    nxt|=(1<<dep);
                    gx=gx/ct[dep]*(ct[dep]-1);
                }
                self(self,j,dep+1,gx,nxt);
            };
            dfs(dfs,0,0,x,0);
        }
    }
    ll ans=0;
    for(int i=0;i<(1<<c);i++)   ans=(ans+dp[i][n&1][0]+dp[i][n&1][1])%M;
    cout<<(ans%M+M)%M;
}    	
signed main(){
    ios::sync_with_stdio(0),cin.tie(0); 
    int _ =1;
    // cin>>_;
    while(_--)  solve();
    return 0;
}