#include<bits/stdc++.h>
using namespace std;
constexpr int N=2005,M=16;
constexpr int MOD=998244353;
constexpr int prime[M]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int n;
int a[N],ret[N];
int id[N];
int state[N];
int f[N][1<<M][2];
void calc(int l,int r)
{
    for(int i=l;i<=r;i++)
    {
        int u=id[i];
        for(int j=0;j<(1<<M);j++)
            f[i][j][0]=f[i-1][j][0],f[i][j][1]=f[i-1][j][1];
        for(int j=0;j<(1<<M);j++)
            for(int o=0;o<=1;o++)
                if(f[i-1][j][o])
                {
                    int x=a[u];
                    int k=j|state[u];
                    for(int l=0;l<M;l++)
                        if(!((j>>l)&1)&&((k>>l)&1))
                        {
                            x=x*(prime[l]-1)/prime[l];
                        }
                    if(o==0&&ret[u]>1) x=x*(ret[u]-1)/ret[u];
                    f[i][k][1]=(f[i][k][1]+(long long)f[i-1][j][o]*x)%MOD;
                }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int x=a[i];
        for(int j=0;j<M;j++)
            if(x%prime[j]==0)
            {
                while(x%prime[j]==0) x/=prime[j];
                state[i]|=1<<j;
            }
        ret[i]=x;
    }
    iota(id+1,id+n+1,1);
    sort(id+1,id+n+1,[&](const int &x,const int &y){return ret[x]<ret[y];});
    f[0][0][0]=1;
    for(int i=1,j=1;i<=n;i=j)
    {
        while(j<=n&&ret[id[i]]==ret[id[j]]) j++;
        calc(i,j);
        for(int s=0;s<(1<<M);s++)
            f[j-1][s][0]=(f[j-1][s][0]+f[j-1][s][1])%MOD,f[j-1][s][1]=0;
    }
    int ans=0;
    for(int j=0;j<(1<<M);j++)
        ans=(ans+f[n][j][0])%MOD;
    cout<<ans;
    return 0;
}