#include <bits/stdc++.h>
#define fi first 
#define se second
using namespace std;
#define pb push_back
#define ls (u << 1)
#define rs (u << 1 | 1)

typedef long long LL;
typedef pair<int, int> PII;

// #define debug(args...) {}
#define debug(args...) { \
     string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
     stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << '\n';}
void err(istream_iterator<string> it){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << ' ';
    err(++it, args...);
}

const int N = 3005;
const int MOD = 998244353;
int p[N], st[N], cnt;
void get_p() {
    for (int i = 2; i < N; i++) {
        if (!st[i]) p[++cnt] = i;
        for (int j = 1; p[j] * i < N; j++) {
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
}

void add(LL &x, LL y) {
    x = (x + y) % MOD;
}

LL qpow(LL a, LL b = MOD - 2, int p = MOD) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p; b >>= 1;
    }
    return res;
}

void solve() {
    int num = 0;
    vector<int> id(60);
    for (int i = 1; i <= cnt; i++) {
        if (p[i] <= 60) id[p[i]] = num++;
    }
    int s2m = 1 << num;

    int n; cin >> n;
    vector<int> big(n + 5);
    vector<vector<PII>> pri(n + 5);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        for (int j = 2; j * j <= x; j++) {
            if (x % j == 0) {
                pri[i].pb({j, 0});
                while (x % j == 0) pri[i].back().se++, x /= j;
            }
        }
        if (x != 1) {
            pri[i].pb({x, 1});
            if (x > 60) big[i] = x;
            // big[i] = x; // debug
        }
    }

    vector<LL> sta(n + 5), val(n + 5, 1);
    for (int i = 1; i <= n; i++) {
        for (auto [x, c] : pri[i]) {
            if (x <= 60) sta[i] |= 1 << id[x];
            // if (x <= 1) sta[i] |= 1 << id[x]; // debug
            for (int j = 1; j <= c; j++) val[i] = val[i] * x % MOD;
        }
    }

    vector<LL> f(s2m); f[0] = 1;
    for (int i = 1; i <= n; i++) {
        vector<LL> g(s2m);
        if (!big[i]) {
            for (int j = 0; j < s2m; j++) {
                add(g[j], f[j]); // not pick 
                add(g[j | sta[i]], f[j] * val[i]); // pick
            }
            swap(f, g);
        }
    }

    vector<array<LL, 2>> fuck(s2m);
    for (int j = 0; j < s2m; j++) fuck[j][0] = f[j];
    // for (int j = 0; j < s2m; j++) if (f[j]) debug(j, f[j]);

    for (int t = 1; t <= cnt; t++) {
        // if (p[t] <= 60) continue;
        int ok = false;
        for (int i = 1; i <= n; i++) {
            if (big[i] != p[t]) continue;
            ok = true;
            vector<array<LL, 2>> guck(s2m);
            for (int j = 0; j < s2m; j++) {
                for (int k = 0; k < 2; k++) add(guck[j][k], fuck[j][k]); // not pick
                for (int k = 0; k < 2; k++) add(guck[j | sta[i]][1], fuck[j][k] * val[i] % MOD); // pick
            }
            swap(fuck, guck);
        }
        if (ok) {
            for (int j = 0; j < s2m; j++) {
                // if (fuck[j][0] || fuck[j][1]) debug(j, fuck[j][0], fuck[j][1]);
                add(fuck[j][0], fuck[j][1] * qpow(p[t]) % MOD * (p[t] - 1));
                fuck[j][1] = 0;
            }
        }
    }
    LL res = 0;
    for (int j = 0; j < s2m; j++) {
        LL now = fuck[j][0];
        for (int k = 0; k < num; k++) {
            if (j >> k & 1) now = now * qpow(p[k + 1]) % MOD * (p[k + 1] - 1) % MOD;
        }
        res += now;
    }
    res %= MOD;
    cout << res << "\n";
}

int main() {
    get_p();
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1; //cin >> tt;
    while (tt--) solve();
    return 0;
}
/*
g++ std.cpp -Wall --extra -o std && ./std < in.txt > out.txt
*/