#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3010;
ll mod=998244353;
ll n;
ll pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll a[N],s[N],v[N];
ll id[N];
ll st[1<<16];
ll dp[1<<16];
ll add_dp[1<<16];
ll tp[1<<16];
ll add_tp[1<<16];
bool cmp(ll x,ll y)
{
    return v[x]<v[y];
}
ll fastpow(ll x,ll p)
{
    ll base=x;
    ll res=1ll;
    while(p)
    {
        if(p&1ll)res=(res*base)%mod;
        base=(base*base)%mod;
        p>>=1ll;
    }
    return res;
}
ll mod_inverse(ll x)
{
    ll res=fastpow(x,mod-2);
    return res;
}
int main()
{
    scanf("%lld",&n);
    ll one_cnt=0ll;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(a[i]==1ll)one_cnt++;
        id[i]=i*1ll;
        ll temp=a[i];
        ll max_p=1ll;
        for(int j=0;j<16;j++)
        {
            while(temp%pri[j]==0)
            {
                temp/=pri[j];
                s[i]|=1ll<<j;
                max_p=pri[j]*1ll;
            }
        }
        if(temp>1)v[i]=temp;
        else v[i]=max_p;
    }
    sort(id+1,id+1+n);
    for(ll mask=0;mask<1ll<<16;mask++)
    {
        ll temp=1ll;
        for(int j=0;j<16;j++)
        {
            if(mask&(1ll<<j))
            {
                temp=(temp*(pri[j]-1ll))%mod;
                temp=(temp*mod_inverse(pri[j]))%mod;
            }
        }
        st[mask]=temp;
    }
    dp[0]=1ll;
    ll pre_prime=1ll;
    for(int i=1;i<=n;i++)
    {
        if(a[id[i]]==1ll)continue;
        for(ll mask=0;mask<(1ll<<16);mask++)
        {
            add_dp[mask]=0ll;
            add_tp[mask]=0ll;
        }
        if(v[id[i]]<=53)
        {
            for(ll mask=0;mask<(1<<16);mask++)
            {
                if(dp[mask]>=1ll)
                {
                    add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+(((dp[mask]*a[id[i]]*1ll)%mod))%mod)%mod;
                }
            }
            for(ll mask=0;mask<(1<<16);mask++)
            {
                dp[mask]=(dp[mask]+add_dp[mask])%mod;
            }
        }
        else
        {
            if(v[id[i]]!=pre_prime)
            {
                for(ll mask=0;mask<(1ll<<16);mask++)
                {
                    dp[mask]=(dp[mask]+tp[mask])%mod;
                    tp[mask]=0ll;
                }
            }
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                if(dp[mask]>=1ll)
                {
                    ll num=(((dp[mask]*a[id[i]]*1ll)%mod))%mod;
                    num=(((num*(v[id[i]]-1ll))%mod)*mod_inverse(v[id[i]]))%mod;
                    add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+num*1ll)%mod;
                }
                if(tp[mask]>=1ll)
                {
                    add_tp[mask|s[id[i]]]=(add_tp[mask|s[id[i]]]+(((tp[mask]*a[id[i]]*1ll)%mod))%mod)%mod;
                }
            }
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                tp[mask]=(((tp[mask]+add_dp[mask])%mod)+add_tp[mask])%mod;
                if(i==n)dp[mask]=(dp[mask]+tp[mask])%mod;
            }
            pre_prime=v[id[i]];
        }
    }
    ll ans=0ll;
    for(ll mask=0;mask<(1<<16);mask++)
    {
        ans=(((ans+(dp[mask]*st[mask])%mod)%mod)+(tp[mask]*0ll)%mod)%mod;
    }
    ans=(ans*1ll*fastpow(2ll,one_cnt))%mod;
    printf("%lld\n",ans);
    return 0;
}
/*
20
1 1 11 121 255 289 1888 885 788 1145 2242 2714 2211 2948 2803 2927 764 661 1858 1949
372472595
*/