#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3007;
const int mod = 998244353;
int n;
vector<int> P;
bool visP[N];
void InitPrime() {
    visP[1] = 1;
    for(int i=2;i<N;++i) {
        if(!visP[i]) P.push_back(i);
        for(auto p : P) {
            if(p*i >= N) break;
            visP[p * i] = 1;
            if(i%p == 0) break;
        }
    }
}
typedef pair<int,int> pii;
#define mp make_pair
vector<pair<pii, vector<int>>> vec[N];
int MaxFac(int x,int &s,vector<int> &cnt) {
    for(int i=0;i<16;++i) {
        auto p = P[i];
        if(x%p == 0) s |= (1ll << i);
        while(x%p == 0) x /= p, ++cnt[i];
    }
    return x;
}
const int M = 16;
const int S = (1<<M);
int f[2][S][2];
void add(int &x,int y) {
    x = (x + y) % mod;
}
void mul(int &x,int y) {
    x = (long long)x * y % mod;
}
/*int Pow(int x,int y) {
    if(y <= 0) return 1;
    int res = 1, base = x;
    while(y) {
        if(y&1) res = res*base % mod;
        base = base*base % mod;
        y >>= 1;
    }
    return res;
}*/
int Pow[16][N];
void InitPow() {
    for(int i=0;i<16;++i) {
        Pow[i][0] = 1;
        for(int j=1;j<N;++j) {
            Pow[i][j] = Pow[i][j-1] * P[i] % mod;
        }
    }
}
void solve() {
    InitPow();
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin >> a[i];

    set<int> st;
    for(auto x : a) {
        int s = 0;
        vector<int> cnt(16, 0);
        int fac = MaxFac(x, s, cnt);
        vec[fac].push_back(mp(mp(x, s), cnt));
        st.insert(fac);
    }
    int now = 1, last = 0;
    f[last][0][1] = 1;
    for(auto y : st) {
        for(int s=0;s<S;++s) {
            add(f[last][s][0], f[last][s][1]);
            f[last][s][1] = 0;
        }
        //cout << "test:: " << f[last][0][0] << "\n";
        for(auto [tmp, xcnt] : vec[y]) {
            auto [x, xs] = tmp;
            for(int s=0;s<S;++s) {
                f[now][s][0] = f[last][s][0];
                f[now][s][1] = f[last][s][1];
            }
            for(int s=0;s<S;++s) {
                int fir = xs & (xs^s);
                int sec = xs & (s);
                int val = 1;
                for(int j=0;j<16;++j) {
                    if(fir & (1ll<<j)) mul(val, P[j]-1);
                    if(sec & (1ll<<j)) mul(val, P[j]);
                    //val = val*Pow(P[j], xcnt[j]-1);
                    if(xcnt[j]-1 >= 1) val = val*Pow[j][xcnt[j]-1]%mod;
                    //if((fir & (1ll<<j) )==(sec & (1ll<<j)) && ((fir & (1ll<<j)) == 1)) cout << "wa" << "\n";
                }
                add(f[now][s|xs][1], f[last][s][0]*val%mod*(max(1ll, y-1))%mod);
                add(f[now][s|xs][1], f[last][s][1]*val%mod*(y)%mod);
            }
            now ^= 1, last ^= 1;
        }
    }
    int ans = 0;
    for(int s=0;s<S;++s) {
        //cout << f[last][s][0] << " " << f[last][s][1] << "\n";
        add(ans, f[last][s][0]+f[last][s][1]);
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    InitPrime();
    solve();
    return 0;
}