# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
    T x=0; bool f=0; char s;
    while(!isdigit(s=getchar())) f|=(s=='-');
    for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return f? -x: x;
}
template <class T>
inline void write(T x) {
    static int writ[50], w_tp=0;
    if(x<0) putchar('-'), x=-x;
    do writ[++w_tp]=x-x/10*10, x/=10; while(x);
    while(putchar(writ[w_tp--]^48), w_tp);
}

# include <vector>
# include <algorithm>
using namespace std;
typedef long long ll;

const int lim = 1<<16;
const int MAXN = 3005;
const int mod = 998244353;
const int P[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

int n, p[MAXN], ID[MAXN];
ll dp[1<<17];
struct node {
	int num, w;
};
vector <node> fac[MAXN];

void divide(int x, int id) {
	for(int i=2; i*i<=x; ++i) {
		if(x%i) continue;
		int cnt = 0;
		while(x%i==0) {
			x /= i;
			++ cnt;
		}
		fac[id].push_back((node){i, cnt});
	}
	if(x>1) fac[id].push_back((node){x, 1});
	reverse(fac[id].begin(), fac[id].end());
	// printf("%d %d\n", fac[id][0].num, fac[id][0].w);
}

bool cmp(int x, int y) {
	return fac[x][0].num < fac[y][0].num;
}

int qkpow(int x, int y) {
	int r = 1;
	while(y) {
		if(y&1) r=1ll*r*x%mod;
		x=1ll*x*x%mod; y>>=1;
	} return r;
}

void calculate(int l, int r, int val) {
	if(val!=-1) ID[val] = 16;
	for(int i=l; i<=r; ++i) {
		int Lim = (val==-1? lim-1: (lim<<1)-1);
		for(int j=Lim; j>=0; --j) {
			int state = j; ll mul = 1;
			for(auto x: fac[p[i]]) {
				mul = mul*qkpow(x.num, x.w-1)%mod;
				if(j>>ID[x.num]&1)
					mul = mul*x.num%mod;
				else	
					mul = mul*(x.num-1)%mod,
					state |= (1<<ID[x.num]);
			}
			dp[state] = (dp[state]+mul*dp[j]%mod)%mod;
		}
	}
	for(int i=0; i<lim; ++i)
		dp[i] = (dp[i]+dp[i+lim+1])%mod,
		dp[i+lim+1] = 0;
}

int main() {
	// freopen("r.in","r",stdin);
	for(int i=0; i<16; ++i)
		ID[P[i]] = i;
	n = read(9);
	int cnt1 = 0, cntr = 0;
	for(int i=1; i<=n; ++i) {
		int x = read(9);
		if(x==1) {
			++ cnt1; continue;
		}
		++ cntr;
		divide(x, cntr);
		p[cntr] = cntr;
	}	
	n = cntr;
	sort(p+1, p+n+1, cmp);
	dp[0] = 1;
	int l=1, r=0;
	while(r<n && fac[p[r+1]][0].num<=53) ++r;
	if(l<=r) calculate(l, r, -1); 
	l=r+1, r=l;
	for(; r<=n; l=r+1, r=l) {
		while(r<n && fac[p[r+1]][0].num==fac[p[l]][0].num) ++r;
		calculate(l, r, fac[p[l]][0].num);
	} 
	ll ans = 0;
	for(int i=0; i<lim; ++i)
		ans = (ans+dp[i])%mod;
	print(ans*qkpow(2,cnt1)%mod, '\n');
	return 0;
}