#include <bits/stdc++.h>

using namespace std; const int maxn = 1e2 + 5, mod = 998244353, maxm = 2e3 + 5; typedef long long ll;

int n, a[maxn];

map<int, int> mp;

inline void add(int x)
{
	for (int i = 2; i * i <= x; i++) if (x % i == 0) while (x % i == 0) mp[i]++, x /= i;
	if (x != 1) mp[x]++;
}

int C[maxm][maxm], F[maxm], P[maxm];



int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), add(a[i]);
	for (int i = 0; i < maxm; i++) for (int j = C[i][0] = 1; j <= i; j++) if ((C[i][j] = C[i - 1][j - 1] + C[i - 1][j]) >= mod) C[i][j] -= mod;
	for (int i = 1; i < maxm; i++) for (int j = 0; j <= i; j += 2) F[i] = (F[i] + (ll)C[i][j] * C[j][j / 2]) % mod;
	for (int i = P[0] = 1; i < maxm; i++) P[i] = (P[i - 1] * 3ll) % mod;
	int A = 1, B = 1;
	for (auto it = mp.begin(); it != mp.end(); it++) A = (ll)A * P[it->second] % mod;
	for (auto it = mp.begin(); it != mp.end(); it++) B = (ll)B * F[it->second] % mod;
	return 0 * printf("%lld\n", (ll)(mod - mod / 2) * (A + B) % mod);
}