#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,47,53,59};
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;
            }
            ll rq=0;
            for(int j=0;j<(1<<c);j++){
                ll gx=x,nxt=0;
                for(int k=0;k<c;k++){
                    if(x%ct[k]==0){
                        nxt|=(1<<k);
                        if(!(j&(1<<k)))    gx=gx/ct[k]*(ct[k]-1);    
                    }  
                }
                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*gx%M)%M;
            }
        }
        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];
            }
            for(int j=0;j<(1<<c);j++){
                ll gx=x,nxt=0;
                for(int k=0;k<c;k++){
                    if(x%ct[k]==0){
                        nxt|=(1<<k);
                        if(!(j&(1<<k)))    gx=gx/ct[k]*(ct[k]-1);    
                    }  
                }
                dp[j|nxt][i&1][1]=(dp[j|nxt][i&1][1]+dp[j][(i-1)&1][0]*(gx/u*(u-1))%M+dp[j][(i-1)&1][1]*gx%M)%M;
            }
        }
    }
    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;
}