#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;
}
int& mul(int &x,int y) {
    return 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;
}*/
const int MAXN=1e5+3;
int Pow[16][MAXN];
void InitPow() {
    for(int i=0;i<16;++i) {
        Pow[i][0] = 1;
        for(int j=1;j<MAXN;++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(!(xs&(1<<j)))continue;
                    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) mul(val, Pow[j][xcnt[j]-1]);
                    //if((fir & (1ll<<j) )==(sec & (1ll<<j)) && ((fir & (1ll<<j)) == 1)) cout << "wa" << "\n";
                }
                add(f[now][s|xs][1], mul(mul(f[last][s][0], val), max(1, y-1)) );
                add(f[now][s|xs][1], mul(mul(f[last][s][1], val), y) );
            }
            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;
}

answer.code: In function ‘void solve()’:
answer.code:100:70: error: no matching function for call to ‘max(int, long long int)’
  100 |                 add(f[now][s|xs][1], mul(mul(f[last][s][0], val), max(1, y-1)) );
      |                                                                   ~~~^~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:100:70: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
  100 |                 add(f[now][s|xs][1], mul(mul(f[last][s][0], val), max(1, y-1)) );
      |                                                                   ~~~^~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:100:70: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
  100 |                 add(f[now][s|xs][1], mul(mul(f[last][s][0], val), max(1, y-1)) );
      |                                                                   ~~~^~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:100:70: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  100 |                 add(f[now][s|xs][1], mul(mul(f[last][s][0], val), max(1, y-1)) );
      |                                                                   ~~~^~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:100:70: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  100 |                 add(f[now][s|xs][1], mul(mul(f[last][s][0], val), max(1, y-1)) );
      |                                                                   ~~~^~~~~~~~