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

const int N = 3E3 + 7, M = 1 << 15, P = 998244353;
int n,m,ans,tot,mx[N],tag[N],val[N],prime[N],a[N],f[N][2][M];

int cmp(int x,int y) { return mx[x] > mx[y]; }

void pls(int &x,int y) { x = (x + y) % P; }

int pow(int a,int p)
{
	int rest = 1;
	for(;p;p >>= 1, a = 1ll * a * a % P)
		if(p & 1) rest = 1ll * rest * a % P;
	return rest;
}

void read(int &x)
{
	char c = getchar(); x = 0;
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

void prepare()
{
	mx[1] = 1;
	for(int i = 2;i < N; ++ i)
	{
		if(!tag[i]) prime[++tot] = mx[i] = i;
		val[i] = 1ll * (i - 1) * pow(i,P - 2) % P;
		
		for(int j = 1;j <= tot; ++ j)
		{
			if(i * prime[j] >= N) break;
			tag[i * prime[j]] = 1, mx[i * prime[j]] = mx[i];
			if(!(i % prime[j])) break;
		}
	}
}

int main()
{
	read(n), prepare();
	for(int i = 1;i <= n; ++ i) read(a[i]);
	
	sort(a + 1,a + n + 1,cmp), m = f[0][0][0] = 1;
	while(n && a[n] == 1) pls(m,m), -- n;
	for(int i = 1,u = 0,v = 1,S;i <= n; ++ i)
	{
		S = 0;
		for(int j = 1;j <= 15; ++ j)
			if(!(a[i] % prime[j])) S |= 1 << j - 1;
		
		if(mx[a[i]] < 53)
		{
			for(int j = 0;j < M; ++ j)
				f[v][0][j] = f[u][0][j] = (f[u][0][j] + f[u][1][j]) % P,
				f[u][1][j] = f[v][1][j] = 0;
			
			for(int j = 0;j < M; ++ j)
				pls(f[v][0][j | S],1ll * f[u][0][j] * a[i] % P);
		}
		else if(i > 1 && mx[a[i]] == mx[a[i - 1]])
		{
			for(int j = 0;j < M; ++ j)
				f[v][0][j] = f[u][0][j], f[v][1][j] = f[u][1][j];
			
			for(int j = 0;j < M; ++ j)
				pls(f[v][1][j | S],1ll * (f[u][0][j] + f[u][1][j]) * a[i] % P * val[mx[a[i]]] % P);
		}
		else
		{
			for(int j = 0;j < M; ++ j)
				f[v][0][j] = f[u][0][j] = (f[u][0][j] + f[u][1][j]) % P,
				f[u][1][j] = f[v][1][j] = 0;
			
			for(int j = 0;j < M; ++ j)
				pls(f[v][1][j | S],1ll * f[u][0][j] * a[i] % P * val[mx[a[i]]] % P);
		}
		
		u ^= 1, v ^= 1;
	}
	
	ans = 0;
	for(int j = 0,x;j < M; ++ j)
	{
		x = 1;
		for(int k = 1;k <= 15; ++ k)
			if(j & (1 << k - 1)) x = 1ll * x * val[prime[k]] % P;
		pls(ans,1ll * (f[n & 1][0][j] + f[n & 1][1][j]) * x % P);
	}
	pls(ans,P), printf("%d\n",1ll * ans * m % P);
	
	return 0;
}