#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
template<class T>inline void MAX(T &a,T b){if(b>a)a=b;}
template<class T>inline void MIN(T &a,T b){if(b<a)a=b;}
template<class T>inline void rd(T &x){
	x=0;char o,f=1;
	while(o=getchar(),o<48)if(o=='-')f=-f;
	do x=(x<<3)+(x<<1)+(o^48);
	while(o=getchar(),o>47);
	x*=f;
}
const int M=3005;
const int S=1<<16;
const int P=998244353;
int fast(int a,int b=P-2){
	int res=1;
	while(b){
		if(b&1)res=1ll*res*a%P;
		a=1ll*a*a%P;
		b>>=1;
	}
	return res;
}
int n,A[M],s[M],mx[M],p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int f[S],g[S],dp[2][S][2];
bool cmp(int a,int b){
	return mx[a]<mx[b];
}
void add(int &a,ll b){
	a=(a+b)%P;
}
void solve(){
	for(int i=1;i<M;i++){
		int x=i;
		for(int j=0;j<16;j++)while(x%p[j]==0)x/=p[j];
		if(x>1)mx[i]=x;
	}
	cin>>n;
	for(int i=1;i<=n;i++)cin>>A[i];
	sort(A+1,A+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=0;j<16;j++)if(A[i]%p[j]==0)s[i]|=1<<j;
	}
	for(int i=0;i<S;i++){
		f[i]=1;
		for(int j=0;j<16;j++)if(i>>j&1)f[i]=1ll*f[i]*(1-fast(p[j])+P)%P;
		g[i]=fast(f[i]);
	}
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++){
		int cur=i&1;
		for(int j=0;j<S;j++)dp[cur][j][0]=dp[cur][j][1]=0;
		for(int j=0;j<S;j++){
			if(s[i]==s[i-1]){
				if(s[i]){
					add(dp[cur][j|s[i]][1],1ll*dp[!cur][j][0]*A[i]%P*g[j]%P*f[j|s[i]]%P*(1-fast(mx[A[i]])+P));
				}
				else{
					add(dp[cur][j|s[i]][1],1ll*dp[!cur][j][0]*A[i]%P*g[j]%P*f[j|s[i]]);
				}
				add(dp[cur][j|s[i]][1],1ll*dp[!cur][j][1]*A[i]%P*g[j]%P*f[j|s[i]]);
				add(dp[cur][j][0],dp[!cur][j][0]);
				add(dp[cur][j][1],dp[!cur][j][1]);
			}
			else{
				if(s[i]){
					add(dp[cur][j|s[i]][1],1ll*dp[!cur][j][0]*A[i]%P*g[j]%P*f[j|s[i]]%P*(1-fast(mx[A[i]])+P));
					add(dp[cur][j|s[i]][1],1ll*dp[!cur][j][1]*A[i]%P*g[j]%P*f[j|s[i]]%P*(1-fast(mx[A[i]])+P));
				}
				else{
					add(dp[cur][j|s[i]][1],1ll*dp[!cur][j][0]*A[i]%P*g[j]%P*f[j|s[i]]);
					add(dp[cur][j|s[i]][1],1ll*dp[!cur][j][1]*A[i]%P*g[j]%P*f[j|s[i]]);
				}
				add(dp[cur][j][0],dp[!cur][j][0]);
				add(dp[cur][j][0],dp[!cur][j][1]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<S;i++)ans=(1ll*ans+dp[n&1][i][0]+dp[n&1][i][1])%P;
	printf("%d\n",ans);
}
int main(){
#ifndef ONLINE_JUDGE
//	freopen("nudun.in","r",stdin);
//	freopen("nudun.out","w",stdout);
#endif
	int cas=1;
	// rd(cas);
	while(cas--)solve();
	return 0;
}