#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
using ll = long long;
const int mod = 998244353;
const int unit = 47;
const int maxn = (1<<15) + 10;
const int all = (1<<15) - 1;
const int N = 15;
vector<pair<ll,int>> vec[3010];
ll dp1[(1<<16)+10],dp2[(1<<16)+10],g[2][(1<<16)+10];
int bit[60],p[20],a[2010];
ll inv[3005];
ll qpow(ll n,ll m)
{
    if(m<0)
    {
        return qpow(qpow(n,mod-2),-m);
    }
    n%=mod;
    ll res=1;
    while(m)
    {
        if(m&1)
        {
            res=res*n%mod;
        }
        n=n*n%mod;
        m>>=1;
    }
    return res;
}
void calc(int i)//calc dp2
{
    for(int s=0;s<=all;s++)
    {
        g[0][s]=g[1][s]=0;
    }
    int pos=0;
    for(auto [v,s1] : vec[i])
    {
        for(int s=0;s<=all;s++)
        {
            g[pos][s]=g[pos^1][s];
        }
        (g[pos][s1]+=v)%=mod;
        for(int s=0;s<=all;s++)
        {
            if((s&s1)==s1)
            {
                for(int s2=s1;s2;s2=s1&(s2-1))
                {
                    (g[pos][s]+=v*g[pos^1][s2|(s1^s)]%mod)%=mod;
                }
                (g[pos][s]+=v*g[pos^1][s1^s]%mod)%=mod;
            }
        }
        pos^=1;
    }
    for(int s=0;s<=all;s++)
    {
        if(i!=1)
        {
            dp2[s]=g[pos^1][s]*(i-1)%mod*inv[i]%mod;
        }
        else
        {
            dp2[s]=g[pos^1][s];
        }
    }
    dp2[0]++;
}
void OR(ll *f,int x=1)
{
    for(int d=2,k=1;d<=(1<<N);d<<=1,k<<=1)
    {
        for(int i=0;i<(1<<N);i+=d)
            for(int j=0;j<k;j++)
            {
                (f[i+j+k]+=f[i+j]*(x+mod))%=mod;
            }
    }
}
void merge(void)//merge dp1 and dp2 to dp1
{
    OR(dp1,1);
    OR(dp2,1);
    for(int i=0;i<(1<<N);i++)
        dp1[i]=dp1[i]*dp2[i]%mod;
    OR(dp1,-1);
}
void solve(void)
{
    int now=0;
    for(int i=2;i<=unit;i++)
    {
        bool valid=true;
        for(int j=2;j<i;j++)
        {
            if(i%j==0)
            {
                valid=false;
                break;
            }
        }
        if(valid)
        {
            bit[i]=now++;
            p[now-1]=i;
        }
    }
    int n;
    //n=2000;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        //a[i]=i;
        now=a[i];
        int s=0;
        for(int j=2;j<=unit;j++)
        {
            while(now%j==0)
            {
                s|=(1<<bit[j]);
                now/=j;
            }
        }
        vec[now].emplace_back(a[i],s);
    }
    dp1[0]=1;
    for(int i=1;i<=3000;i++)
    {
        if(vec[i].empty())
        {
            continue;
        }
        calc(i);
        merge();
    }
    ll ans=0;
    for(int s=0;s<=all;s++)
    {
        for(int i=0;i<N;i++)
        {
            if(s>>i&1)
            {
                (dp1[s]*=(p[i]-1)*inv[p[i]]%mod)%=mod;
            }
        }
        (ans+=dp1[s])%=mod;
    }
    cout<<ans<<endl;
    //cout<<clock()*1.0/CLOCKS_PER_SEC<<endl;
}
signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<=3000;i++)
        inv[i]=qpow(i,-1);
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}