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

// #define int long long

typedef pair<int, int> pii;
typedef long long LL;
typedef unsigned long long uLL;

const int inf32 = 1e9;
const LL inf64 = 1e18;

const int P = 998244353;
template<const int mod>
struct ModInt {
    static const int P = mod;
    int x;
    ModInt (int x = 0) : x(x % P) {}
    ModInt (LL x) : x(int(x % P)) {}
    int val() {return x;}

    ModInt operator + (const ModInt &a) const {int x0 = x + a.x; return ModInt(x0 < P ? x0 : x0 - P);}
    ModInt operator - (const ModInt &a) const {int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + P : x0);}
    ModInt operator * (const ModInt &a) const {return ModInt(1ll * x * a.x % P);}
    ModInt operator / (const ModInt &a) const {return *this * a.inv();}
    bool operator == (const ModInt &a) const {return x == a.x;};
    bool operator != (const ModInt &a) const {return x != a.x;};
    void operator += (const ModInt &a) {x += a.x; if (x >= P) x -= P;}
    void operator -= (const ModInt &a) {x -= a.x; if (x < 0) x += P;}
    void operator *= (const ModInt &a) {x = 1ll * x * a.x % P;}
    void operator /= (const ModInt &a) {*this = *this / a;}
    friend ModInt operator + (int y, const ModInt &a){int x0 = y + a.x; return ModInt(x0 < P ? x0 : x0 - P);}
    friend ModInt operator - (int y, const ModInt &a){int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + P : x0);}
    friend ModInt operator * (int y, const ModInt &a){return ModInt(1ll * a.x * y % P);}
    friend ModInt operator / (int y, const ModInt &a){return ModInt(y) / a;}
    friend ostream &operator<<(ostream &os, const ModInt &a) {return os << (a.x + P) % P;}
    friend istream &operator>>(istream &is, ModInt &t) {return is >> t.x;}

    ModInt pow(LL n) const {
       ModInt sum(1), base(x);
       n %= (P - 1);
       while (n) {
           if (n & 1) sum *= base;
           base *= base;
           n >>= 1;
       }
       return sum;
    }

    ModInt inv() const {
        int a = x, b = P, x = 1, y = 0;
        while (b) {
        int t = a / b;
           a -= t * b; swap(a, b);
           x -= t * y; swap(x, y);
        }
        if (x < 0) y += P;
        return x;
    }
};
using mint = ModInt<P>;

const int maxn = 3000;

int isprime[maxn], prime[maxn];
int prime_cnt = 0;

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isprime[i]) {prime[++prime_cnt] = i;}
        for (int j = 1; j <= prime_cnt; j++) {
            if (prime[j] * i > n) break;
            isprime[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

struct node {
    LL a, v, p;
};

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);

    init(3e3);

    int T = 1;
    // T = read();
    while (T--) {
        int n;
        cin >> n;
        vector<node> a(n + 5, {0, 0, 0});
        for (int i = 1; i <= n; i++) cin >> a[i].a;

        LL M = 16 + 1;

        for (int i = 1; i <= n; i++) {
            int x = a[i].a, v = 0;
            for (int j = 1; j <= M - 1; j++) {
                while (x % prime[j] == 0) {
                    x /= prime[j];
                    v |= (1 << (j - 1));
                }
            }
            if (x >= 2) v |= 1 << (M - 1);
            a[i].v = v;
            a[i].p = x;
        }
        sort(a.begin() + 1, a.begin() + 1 + n, [&](node x, node y){
            return x.p < y.p;
        });

        vector<mint> dp((1 << M) + 5, 0);
        auto lst = dp;

        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            swap(dp, lst);
            if (a[i].p != a[i - 1].p) {
                for (int j = (1 << (M - 1)); j < (1 << M); j++) lst[j ^ (1 << (M - 1))] += lst[j], dp[j] = lst[j] = 0;
            }
            for (int j = 0; j < (1 << (M - 1)); j++) dp[j] = lst[j];

            auto [x, v, p] = a[i];
            prime[M] = p;

            for (int j = 0; j < (1 << M); j++) {
                mint tmp = lst[j];
                if (tmp == 0) continue;
                for (int k = 0; k < M; k++) {
                    if (!(j >> k & 1) && (v >> k & 1)) {
                        tmp *= mint(1) - mint(1) / (prime[k + 1]);
                    }
                }
                dp[j | v] += tmp * x;
            }
        }

        mint ans = 0;
        for (int i = 0; i < (1 << M); i++) ans += dp[i];
        cout << ans << "\n";

    }

    return 0;
}