#include <iostream>
#include <cstdio>
using namespace std;

const int N = 3010;
const int mod = 998244353;
long long n;
long long pri[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
long long a[N], s[N], v[N];
long long id[N];
long long st[1 << 16];
long long dp[1 << 16];
long long add_dp[1 << 16];
long long tp[1 << 16];
long long add_tp[1 << 16];

bool cmp(long long x, long long y) {
    return v[x] < v[y];
}

long long fastpow(long long x, long long p) {
    long long base = x;
    long long res = 1;
    while (p) {
        if (p & 1) {
            res = (res * base) % mod;
        }
        base = (base * base) % mod;
        p >>= 1;
    }
    return res;
}

long long mod_inverse(long long x) {
    long long res = fastpow(x, mod - 2);
    return res;
}

int main() {
    scanf("%lld", &n);
    long long one_cnt = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        if (a[i] == 1) one_cnt++;
        id[i] = i;
        long long temp = a[i];
        long long max_p = 1;
        for (int j = 0; j < 16; j++) {
            while (temp % pri[j] == 0) {
                temp /= pri[j];
                s[i] |= 1 << j;
                max_p = pri[j];
            }
        }
        if (temp > 1) v[i] = temp;
        else v[i] = max_p;
    }
    sort(id + 1, id + n + 1, cmp);
    for (long long mask = 0; mask < (1 << 16); mask++) {
        long long temp = 1;
        for (int j = 0; j < 16; j++) {
            if (mask & (1 << j)) {
                temp = (temp * (pri[j] - 1)) % mod;
                temp = (temp * mod_inverse(pri[j])) % mod;
            }
        }
        st[mask] = temp;
    }
    dp[0] = 1;
    long long pre_prime = 1;
    for (int i = 1; i <= n; i++) {
        if (a[id[i]] == 1) continue;
        fill(add_dp, add_dp + (1 << 16), 0);
        fill(add_tp, add_tp + (1 << 16), 0);
        if (v[id[i]] <= 53) {
            for (long long mask = 0; mask < (1 << 16); mask++) {
                if (dp[mask] >= 1) {
                    add_dp[mask | s[id[i]]] = (add_dp[mask | s[id[i]]] + (st[(mask | s[id[i]]) ^ mask] * ((dp[mask] * a[id[i]]) % mod)) % mod) % mod;
                }
            }
            for (long long mask = 0; mask < (1 << 16); mask++) {
                dp[mask] = (dp[mask] + add_dp[mask]) % mod;
            }
        } else {
            if (v[id[i]]!= pre_prime) {
                for (long long mask = 0; mask < (1 << 16); mask++) {
                    dp[mask] = (dp[mask] + tp[mask]) % mod;
                    tp[mask] = 0;
                }
            }
            for (long long mask = 0; mask < (1 << 16); mask++) {
                if (dp[mask] >= 1) {
                    long long num = (st[(mask | s[id[i]]) ^ mask] * ((dp[mask] * ((v[id[i]] - 1) * (a[id[i]] / v[id[i]]))) % mod)) % mod;
                    add_dp[mask | s[id[i]]] = (add_dp[mask | s[id[i]]] + num) % mod;
                }
                if (tp[mask] >= 1) {
                    add_tp[mask | s[id[i]]] = (add_tp[mask | s[id[i]]] + (st[(mask | s[id[i]]) ^ mask] * ((tp[mask] * a[id[i]]) % mod)) % mod) % mod;
                }
            }
            for (long long mask = 0; mask < (1 << 16); mask++) {
                tp[mask] = ((tp[mask] + add_dp[mask]) % mod + add_tp[mask]) % mod;
            }
            pre_prime = v[id[i]];
        }
    }
    long long ans = 0;
    for (long long mask = 0; mask < (1 << 16); mask++) {
        ans = ((ans + dp[mask]) % mod + tp[mask]) % mod;
    }
    ans = (ans * fastpow(2, one_cnt)) % mod;
    printf("%lld\n", ans);
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:58:5: error: ‘sort’ was not declared in this scope; did you mean ‘short’?
   58 |     sort(id + 1, id + n + 1, cmp);
      |     ^~~~
      |     short
answer.code:40:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
answer.code:43:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |         scanf("%lld", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~~~