#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>>=1;
    }
    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]|=1<<j;
                max_p=pri[j];
            }
        }
        if(temp>1)v[i]=temp;
        else v[i]=max_p;
    }
    sort(id+1,id+1+n);
    for(int mask=0;mask<1<<16;mask++)
    {
        ll temp=1ll;
        for(int j=0;j<16;j++)
        {
            if(mask&(1<<j))
            {
                temp=(temp*(pri[j]-1ll))%mod;
                temp=(temp*mod_inverse(pri[j]))%mod;
            }
        }
        st[mask]=temp;
    }
    dp[0]=1ll;
    dp[s[id[1]]]=(a[id[1]]*st[s[id[1]]])%mod;
    if(v[id[1]]>53)
    {
        dp[s[id[1]]]=(dp[s[id[1]]]*(v[id[1]]-1ll))%mod;
        dp[s[id[1]]]=(dp[s[id[1]]]*mod_inverse(v[id[1]]))%mod;
    }
    int pre_prime=v[id[1]];
    for(int i=2;i<=n;i++)
    {
        if(a[id[i]]==1ll)continue;
        for(int mask=0;mask<1<<16;mask++)
        {
            add_dp[mask]=0ll;
            add_tp[mask]=0ll;
        }
        if(v[id[i]]<=53)
        {
            for(int mask=0;mask<1<<16;mask++)
            {
                if(dp[mask]>=1ll)
                {
                    add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+(st[(mask|s[id[i]])^mask]*(dp[mask]*a[id[i]]*1ll)%mod)%mod)%mod;
                }
            }
            for(int mask=0;mask<1<<16;mask++)
            {
                dp[mask]=(dp[mask]+add_dp[mask])%mod;
            }
            /*
            for(int mask=0;mask<4;mask++)
            {
                printf("%lld ",dp[mask]);
            }
            printf("\n");
            */
        }
        else
        {
            if(v[id[i]]!=pre_prime)
            {
                for(int mask=0;mask<1<<16;mask++)
                {
                    dp[mask]=(dp[mask]+tp[mask])%mod;
                    tp[mask]=0ll;
                }
            }
            for(int mask=0;mask<1<<16;mask++)
            {
                if(dp[mask]>=1ll)
                {
                    ll num=(st[(mask|s[id[i]])^mask]*(dp[mask]*a[id[i]]*1ll)%mod)%mod;
                    num=(((num*(v[i]-1ll))%mod)*mod_inverse(v[i]))%mod;
                    add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+num)%mod;
                }
                if(tp[mask]>=1ll)
                {
                    add_tp[mask|s[id[i]]]=(add_tp[mask|s[id[i]]]+(st[(mask|s[id[i]])^mask]*(tp[mask]*a[id[i]]*1ll)%mod)%mod)%mod;
                }
            }
            for(int mask=0;mask<1<<16;mask++)
            {
                tp[mask]=(((tp[mask]+add_dp[mask])%mod)+add_tp[mask])%mod;
                if(i==n)dp[mask]=(dp[mask]+tp[mask])%mod;
            }
        }
    }
    ll ans=0ll;
    for(int mask=0;mask<1<<16;mask++)ans=(ans+dp[mask])%mod;
    ans=(ans*fastpow(2ll,one_cnt))%mod;
    printf("%lld\n",ans);
    return 0;
}