#include <bits/stdc++.h>

using ll = long long;

constexpr int P = 998244353;

ll mul(ll a, ll b) {
  return a * b % P;
}

ll add(ll a, ll b) {
  ll res = a + b;
  return (res >= P ? res - P : res);
}

ll neg(ll x) {
  return (x == 0 ? x : P - x);
}

ll sub(ll a, ll b) {
  return add(a, neg(b));
}


const int N = 16;
const int V = 3000;
const int S = 20;
const int v = 55;
int pw[v][S + 1];

std::vector<int> minp, primes;
std::vector<int> inv(v + 1), pi;
void sieve(int n) {
  minp.assign(n + 1, 0);
  primes.clear();

  for (int i = 2; i <= n; i++) {
    if (minp[i] == 0) {
      minp[i] = i;
      primes.push_back(i);
    }

    for (int p : primes) {
      if (i * p > n) {
        break;
      }
      minp[i * p] = p;
      if (p == minp[i]) {
        break;
      }
    }
  }

  for (int x : primes) {
    if (x < v) {
      inv[x] = pi.size();
      pi.push_back(x);

      pw[x][0] = 1;
      for (int i = 0; i < S; i++) {
        pw[x][i + 1] = mul(pw[x][i], x);
      }
    } else {
      break;
    }
  }
}


void solve() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  std::map<int, std::vector<int>> map;

  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    if (minp[a[i]] < v) {
      map[-1].push_back(a[i]);
    } else {
      map[minp[a[i]]].push_back(a[i] / minp[a[i]]);
    }
  }

  int s = (1 << (N + 1));
  int si = (1 << (N));
  std::vector<int> f(s, -1);
  f[0] = 1;
  for (auto &[p, arr] : map) {
    for (int x : arr) {
      // std::cout << p << " " << x << " p x \n";
      auto g = f;
      std::vector<int> cnt(pi.size());
      while (x > 1) {
        cnt[inv[minp[x]]]++;
        x /= minp[x];
      }

      for (int sta = 0; sta < si; sta++) {
        if (f[sta] == -1 && f[sta | (1 << N)] == -1) continue;
        int t = 0;
        int tmp = 1;
        for (int i = 0; i < pi.size(); i++) {
          if (cnt[i] > 0) {
            t |= (1 << i);

            if ((sta >> i) & 1) {
              tmp = mul(tmp, pw[pi[i]][cnt[i]]);
            } else {
              tmp = mul(tmp, sub(pw[pi[i]][cnt[i]], pw[pi[i]][cnt[i] - 1]));
            }
          }
        }

        if (p == -1) {
          if (f[sta] != -1) {
            if (g[t] == -1) g[t] = 0;
            g[t] = add(g[t], mul(tmp, f[sta]));
          }
        } else {
          t |= (1 << N);
          if (f[sta] != -1) {
            if (g[t] == -1) g[t] = 0;
            g[t] = add(g[t], mul(tmp, mul(f[sta], p - 1)));
          }
          if (f[sta | (1 << N)] != -1) {
            if (g[t] == -1) g[t] = 0;
            g[t] = add(g[t], mul(tmp, mul(f[sta | (1 << N)], p)));
          }
        }
      }

      f = std::move(g);
    }

    for (int sta = 0; sta < si; sta++) {
      if (f[sta] == -1) f[sta] = 0;
      if (f[sta | (1 << N)] != -1) {
        f[sta] = add(f[sta], f[sta | (1 << N)]);
      }
    }
  }

  int ans = 0;
  for (int sta = 0; sta < si; sta++) {
    if (f[sta] != -1) {
      // std::cout << sta << "?\n";
      ans = add(ans, f[sta]);
    }
  }
  std::cout << ans;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  sieve(V);
  // sieve(v);
  // std::cout << v;
  solve();

  return 0;
}