#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=3e3+7,maxp=5e2+7,maxs=1<<16,mod=998244353;
const int p[60]={0,2,3,5,7,11,13,17,23,29,31,37,41,43,47,51,53};
int n,ans;
int a[maxn],w[maxn],f[maxp][maxs],g[maxs],h[maxs];
vector<int> big;
vector<int> e[maxn];

/*
f[i+1][s] <- f[i][s]
f[i+1][s^w[i+1]] <- f[i][s]*a[i+1]
*/

int _mod(int x){
	return x>=mod?x-mod:x;
}

int qpow(int x,int y){
	if(!y) return 1;
	if(y==1) return x;
	int val=qpow(x,y>>1ll);
	if(y&1ll) return val*val%mod*x%mod;
	else return val*val%mod;
}

void calc(int x){
	int now=x;
	for(int i=1;i<=16;i++){
		if(!(now%p[i])){
			w[x]|=1<<i-1;
			while(!(now%p[i])) now/=p[i]; 
		}
	}
	e[now].push_back(x);
	big.push_back(now);
	return ;
}

signed main(){
	for(int s=0;s<maxs;s++){
		h[s]=1;
		for(int i=0;i<16;i++){
			if(s&1<<i) h[s]=h[s]*(p[i+1]-1)%mod*qpow(p[i+1],mod-2)%mod;
		}
	}
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(!w[a[i]]) calc(a[i]);
	}
	sort(big.begin(),big.end());
	big.erase(unique(big.begin(),big.end()),big.end());
	int tot=big.size();
	f[0][0]=1;
	for(int i=0;i<tot;i++){
		int num=big[i];
		int mul=(num-1)*qpow(num,mod-2)%mod;
		if(num==1) mul=1;
		for(int s=0;s<maxs;s++) g[s]=f[i][s]*mul%mod;
		for(int j=0;j<e[num].size();j++){
			int val=e[num][j];
			for(int s=maxs-1;s>=0;s--){
				g[s^w[val]]=(g[s^w[val]]+g[s]*val)%mod;
			}
		}
		for(int s=0;s<maxs;s++) f[i+1][s]=(f[i][s]+g[s]-f[i][s]*mul%mod+mod)%mod;
	}
	for(int s=0;s<maxs;s++) ans=(ans+f[tot][s]*h[s])%mod;
//	printf("test:%lld\n",f[1][3]);
	printf("%lld",ans);
	return 0;
}
/*
input:
3
1 2 3

output:
12
*/