#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int > 
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
using namespace std;
const int N = 5007, mod = 998244353, inv2 = (mod + 1) / 2;

int n, a[N];
int A[N], B[N], tot;

map < int, vi > MP;
int pool[N * 4], *dp = pool + N, *ndp = pool + N * 3;
int main() {
//	freopen("tree.in", "r", stdin);
//	freopen("tree.out", "w", stdout);
	ios :: sync_with_stdio(false); 
	cin.tie(0); cout.tie(0);
	cin >> n;
	L(i, 1, n) {
		cin >> a[i];
	}
	L(i, 1, n) {
		ll x = a[i];
		L(p, 2, sqrt(x)) {
			int cnt = 0;
			while(x % p == 0) x /= p, ++cnt;
			++tot, A[tot] = x, B[tot] = cnt;
		}
		if(x > 1) ++tot, A[tot] = x, B[tot] = 1;
	}
	
	int prd = 1;
	L(i, 1, tot) {
		prd = (ll) prd * ((B[i] + 1) * (B[i] + 2) / 2) % mod;
	}
	L(i, 1, tot) {
		MP[A[i]].emplace_back(B[i]);
	}
	
	int ans = 1;
	for(auto u : MP) {
		int sum = 0;
		dp[0] = 1;
		for(auto k : u.second) {
			L(i, -sum, sum) {
				L(x, 0, k) {
					L(y, x, k) {
						(ndp[i + x * 2 - y] += dp[i]) %= mod;
					}
				}
			}
			L(i, -sum, sum) dp[i] = 0;
			sum += k;
			swap(dp, ndp);
		}
		ans = (ll) ans * dp[0] % mod;
		L(i, -sum, sum)
			dp[i] = 0;
	} 
	cout << (ll) (prd + ans) * inv2 % mod << '\n';
	return 0;
}