Problem: All bus tickets in Berland have their numbers. A number consists of n digits (n is even). Only k decimal digits d_1, d_2, ..., d_k can be used to form ticket numbers. If 0 is among these digits, then numbers may have leading zeroes. For example, if n = 4 and only digits 0 and 4 can be used, then 0000, 4004, 4440 are valid ticket numbers, and 0002, 00, 44443 are not.

A ticket is lucky if the sum of first n / 2 digits is equal to the sum of remaining n / 2 digits. 

Calculate the number of different lucky tickets in Berland. Since the answer may be big, print it modulo 998244353.

Input

The first line contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ k ≤ 10) — the number of digits in each ticket number, and the number of different decimal digits that may be used. n is even.

The second line contains a sequence of pairwise distinct integers d_1, d_2, ..., d_k (0 ≤ d_i ≤ 9) — the digits that may be used in ticket numbers. The digits are given in arbitrary order.

Output

Print the number of lucky ticket numbers, taken modulo 998244353.

Examples

Input

4 2
1 8


Output

6


Input

20 1
6


Output

1


Input

10 5
6 1 4 0 3


Output

569725


Input

1000 7
5 4 0 1 8 3 2


Output

460571165

Note

In the first example there are 6 lucky ticket numbers: 1111, 1818, 1881, 8118, 8181 and 8888.

There is only one ticket number in the second example, it consists of 20 digits 6. This ticket number is lucky, so the answer is 1.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <int MOD_>
struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

 private:
  using ll = long long;
  int v;
  static int minv(int a, int m) {
    a %= m;
    assert(a);
    return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  }

 public:
  modnum() : v(0) {}
  modnum(ll v_) : v(int(v_ % MOD)) {
    if (v < 0) v += MOD;
  }
  explicit operator int() const { return v; }
  friend std::ostream& operator<<(std::ostream& out, const modnum& n) {
    return out << int(n);
  }
  friend std::istream& operator>>(std::istream& in, modnum& n) {
    ll v_;
    in >> v_;
    n = modnum(v_);
    return in;
  }
  friend bool operator==(const modnum& a, const modnum& b) {
    return a.v == b.v;
  }
  friend bool operator!=(const modnum& a, const modnum& b) {
    return a.v != b.v;
  }
  modnum inv() const {
    modnum res;
    res.v = minv(v, MOD);
    return res;
  }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD - v : 0;
    return res;
  }
  friend modnum neg(const modnum& m) { return m.neg(); }
  modnum operator-() const { return neg(); }
  modnum operator+() const { return modnum(*this); }
  modnum& operator++() {
    v++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator--() {
    if (v == 0) v = MOD;
    v--;
    return *this;
  }
  modnum& operator+=(const modnum& o) {
    v += o.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  modnum& operator-=(const modnum& o) {
    v -= o.v;
    if (v < 0) v += MOD;
    return *this;
  }
  modnum& operator*=(const modnum& o) {
    v = int(ll(v) * ll(o.v) % MOD);
    return *this;
  }
  modnum& operator/=(const modnum& o) { return *this *= o.inv(); }
  friend modnum operator++(modnum& a, int) {
    modnum r = a;
    ++a;
    return r;
  }
  friend modnum operator--(modnum& a, int) {
    modnum r = a;
    --a;
    return r;
  }
  friend modnum operator+(const modnum& a, const modnum& b) {
    return modnum(a) += b;
  }
  friend modnum operator-(const modnum& a, const modnum& b) {
    return modnum(a) -= b;
  }
  friend modnum operator*(const modnum& a, const modnum& b) {
    return modnum(a) *= b;
  }
  friend modnum operator/(const modnum& a, const modnum& b) {
    return modnum(a) /= b;
  }
};
template <typename T>
T pow(T a, long long b) {
  assert(b >= 0);
  T r = 1;
  while (b) {
    if (b & 1) r *= a;
    b >>= 1;
    a *= a;
  }
  return r;
}
template <typename U, typename V>
struct pairnum {
  U u;
  V v;
  pairnum() : u(0), v(0) {}
  pairnum(long long val) : u(val), v(val) {}
  pairnum(const U& u_, const V& v_) : u(u_), v(v_) {}
  friend std::ostream& operator<<(std::ostream& out, const pairnum& n) {
    return out << '(' << n.u << ',' << ' ' << n.v << ')';
  }
  friend std::istream& operator>>(std::istream& in, pairnum& n) {
    long long val;
    in >> val;
    n = pairnum(val);
    return in;
  }
  friend bool operator==(const pairnum& a, const pairnum& b) {
    return a.u == b.u && a.v == b.v;
  }
  friend bool operator!=(const pairnum& a, const pairnum& b) {
    return a.u != b.u || a.v != b.v;
  }
  pairnum inv() const { return pairnum(u.inv(), v.inv()); }
  pairnum neg() const { return pairnum(u.neg(), v.neg()); }
  pairnum operator-() const { return pairnum(-u, -v); }
  pairnum operator+() const { return pairnum(+u, +v); }
  pairnum& operator++() {
    ++u, ++v;
    return *this;
  }
  pairnum& operator--() {
    --u, --v;
    return *this;
  }
  pairnum& operator+=(const pairnum& o) {
    u += o.u;
    v += o.v;
    return *this;
  }
  pairnum& operator-=(const pairnum& o) {
    u -= o.u;
    v -= o.v;
    return *this;
  }
  pairnum& operator*=(const pairnum& o) {
    u *= o.u;
    v *= o.v;
    return *this;
  }
  pairnum& operator/=(const pairnum& o) {
    u /= o.u;
    v /= o.v;
    return *this;
  }
  friend pairnum operator++(pairnum& a, int) {
    pairnum r = a;
    ++a;
    return r;
  }
  friend pairnum operator--(pairnum& a, int) {
    pairnum r = a;
    --a;
    return r;
  }
  friend pairnum operator+(const pairnum& a, const pairnum& b) {
    return pairnum(a) += b;
  }
  friend pairnum operator-(const pairnum& a, const pairnum& b) {
    return pairnum(a) -= b;
  }
  friend pairnum operator*(const pairnum& a, const pairnum& b) {
    return pairnum(a) *= b;
  }
  friend pairnum operator/(const pairnum& a, const pairnum& b) {
    return pairnum(a) /= b;
  }
};
namespace fft {
template <typename T>
int sz(const T& t) {
  return int(t.size());
}
int nextPow2(int s) { return 1 << (s > 1 ? 32 - __builtin_clz(s - 1) : 0); }
template <typename dbl>
struct cplx {
  dbl x, y;
  cplx(dbl x_ = 0, dbl y_ = 0) : x(x_), y(y_) {}
  friend cplx operator+(cplx a, cplx b) { return cplx(a.x + b.x, a.y + b.y); }
  friend cplx operator-(cplx a, cplx b) { return cplx(a.x - b.x, a.y - b.y); }
  friend cplx operator*(cplx a, cplx b) {
    return cplx(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  }
  friend cplx conj(cplx a) { return cplx(a.x, -a.y); }
  friend cplx inv(cplx a) {
    dbl n = (a.x * a.x + a.y * a.y);
    return cplx(a.x / n, -a.y / n);
  }
};
template <typename num>
struct getRoot {
  static num f(int k) = delete;
};
template <typename dbl>
struct getRoot<cplx<dbl>> {
  static cplx<dbl> f(int k) {
    dbl a = 2 * 3.14159265358979323846264338327950288 / k;
    return cplx<dbl>(cos(a), sin(a));
  }
};
template <int MOD>
struct primitive_root {
  static const int value;
};
template <>
struct primitive_root<998244353> {
  static const int value = 3;
};
template <int MOD>
struct getRoot<modnum<MOD>> {
  static modnum<MOD> f(int k) {
    return pow(modnum<MOD>(primitive_root<MOD>::value), (MOD - 1) / k);
  }
};
template <typename num>
class fft {
  static vector<int> rev;
  static vector<num> rt;

 public:
  static void init(int n);
  template <typename Iterator>
  static void go(Iterator begin, int n);
  static vector<num> scratch_a;
  static vector<num> scratch_b;
};
template <typename num>
vector<int> fft<num>::rev({0, 1});
template <typename num>
vector<num> fft<num>::rt(2, num(1));
template <typename num>
vector<num> fft<num>::scratch_a;
template <typename num>
vector<num> fft<num>::scratch_b;
template <typename num>
void fft<num>::init(int n) {
  if (n <= sz(rt)) return;
  rev.resize(n);
  for (int i = 0; i < n; i++) {
    rev[i] = (rev[i >> 1] | ((i & 1) * n)) >> 1;
  }
  rt.reserve(n);
  for (int k = sz(rt); k < n; k *= 2) {
    rt.resize(2 * k);
    num z = getRoot<num>::f(2 * k);
    for (int i = k / 2; i < k; i++) {
      rt[2 * i] = rt[i], rt[2 * i + 1] = rt[i] * z;
    }
  }
}
template <typename num>
template <typename Iterator>
void fft<num>::go(Iterator begin, int n) {
  init(n);
  int s = __builtin_ctz(sz(rev) / n);
  for (int i = 0; i < n; i++) {
    if (i < (rev[i] >> s)) {
      swap(*(begin + i), *(begin + (rev[i] >> s)));
    }
  }
  for (int k = 1; k < n; k *= 2) {
    for (int i = 0; i < n; i += 2 * k) {
      Iterator it1 = begin + i, it2 = it1 + k;
      for (int j = 0; j < k; j++, ++it1, ++it2) {
        num t = rt[j + k] * *it2;
        *it2 = *it1 - t;
        *it1 = *it1 + t;
      }
    }
  }
}
template <typename num>
struct fft_multiplier {
  template <typename IterA, typename IterB, typename IterOut>
  static void multiply(IterA ia, int sza, IterB ib, int szb, IterOut io) {
    vector<num>& fa = fft<num>::scratch_a;
    vector<num>& fb = fft<num>::scratch_b;
    int s = sza + szb - 1;
    if (s <= 0) return;
    int n = nextPow2(s);
    fft<num>::init(n);
    if (sz(fa) < n) fa.resize(n);
    if (sz(fb) < n) fb.resize(n);
    copy(ia, ia + sza, fa.begin());
    fill(fa.begin() + sza, fa.begin() + n, num(0));
    copy(ib, ib + szb, fb.begin());
    fill(fb.begin() + szb, fb.begin() + n, num(0));
    fft<num>::go(fa.begin(), n);
    fft<num>::go(fb.begin(), n);
    num d = inv(num(n));
    for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] * d;
    reverse(fa.begin() + 1, fa.begin() + n);
    fft<num>::go(fa.begin(), n);
    copy(fa.begin(), fa.begin() + s, io);
  }
};
template <typename num>
struct fft_inverser {
  template <typename IterA, typename IterOut>
  static void inverse(IterA ia, int sza, IterOut io) {
    vector<num>& fa = fft<num>::scratch_a;
    vector<num>& fb = fft<num>::scratch_b;
    if (sza == 0) return;
    int s = nextPow2(sza) * 2;
    fft<num>::init(s);
    if (sz(fa) < s) fa.resize(s);
    if (sz(fb) < s) fb.resize(s);
    fb[0] = inv(*ia);
    for (int n = 1; n < sza;) {
      fill(fb.begin() + n, fb.begin() + 4 * n, num(0));
      n *= 2;
      copy(ia, ia + min(n, sza), fa.begin());
      fill(fa.begin() + min(n, sza), fa.begin() + 2 * n, 0);
      fft<num>::go(fb.begin(), 2 * n);
      fft<num>::go(fa.begin(), 2 * n);
      num d = inv(num(2 * n));
      for (int i = 0; i < 2 * n; i++) fb[i] = fb[i] * (2 - fa[i] * fb[i]) * d;
      reverse(fb.begin() + 1, fb.begin() + 2 * n);
      fft<num>::go(fb.begin(), 2 * n);
    }
    copy(fb.begin(), fb.begin() + sza, io);
  }
};
template <typename dbl>
struct fft_double_multiplier {
  template <typename IterA, typename IterB, typename IterOut>
  static void multiply(IterA ia, int sza, IterB ib, int szb, IterOut io) {
    vector<cplx<dbl>>& fa = fft<cplx<dbl>>::scratch_a;
    vector<cplx<dbl>>& fb = fft<cplx<dbl>>::scratch_b;
    int s = sza + szb - 1;
    if (s <= 0) return;
    int n = nextPow2(s);
    fft<cplx<dbl>>::init(n);
    if (sz(fa) < n) fa.resize(n);
    if (sz(fb) < n) fb.resize(n);
    fill(fa.begin(), fa.begin() + n, 0);
    {
      auto it = ia;
      for (int i = 0; i < sza; ++i, ++it) fa[i].x = *it;
    }
    {
      auto it = ib;
      for (int i = 0; i < szb; ++i, ++it) fa[i].y = *it;
    }
    fft<cplx<dbl>>::go(fa.begin(), n);
    for (auto& x : fa) x = x * x;
    for (int i = 0; i < n; ++i) fb[i] = fa[(n - i) & (n - 1)] - conj(fa[i]);
    fft<cplx<dbl>>::go(fb.begin(), n);
    {
      auto it = io;
      for (int i = 0; i < s; ++i, ++it) *it = fb[i].y / (4 * n);
    }
  }
};
template <typename mnum>
struct fft_mod_multiplier {
  template <typename IterA, typename IterB, typename IterOut>
  static void multiply(IterA ia, int sza, IterB ib, int szb, IterOut io) {
    using cnum = cplx<double>;
    vector<cnum>& fa = fft<cnum>::scratch_a;
    vector<cnum>& fb = fft<cnum>::scratch_b;
    int s = sza + szb - 1;
    if (s <= 0) return;
    int n = nextPow2(s);
    fft<cnum>::init(n);
    if (sz(fa) < n) fa.resize(n);
    if (sz(fb) < n) fb.resize(n);
    {
      auto it = ia;
      for (int i = 0; i < sza; ++i, ++it)
        fa[i] = cnum(int(*it) & ((1 << 15) - 1), int(*it) >> 15);
    }
    fill(fa.begin() + sza, fa.begin() + n, 0);
    {
      auto it = ib;
      for (int i = 0; i < szb; ++i, ++it)
        fb[i] = cnum(int(*it) & ((1 << 15) - 1), int(*it) >> 15);
    }
    fill(fb.begin() + szb, fb.begin() + n, 0);
    fft<cnum>::go(fa.begin(), n);
    fft<cnum>::go(fb.begin(), n);
    double r0 = 0.5 / n;
    for (int i = 0; i <= n / 2; i++) {
      int j = (n - i) & (n - 1);
      cnum g0 = (fb[i] + conj(fb[j])) * r0;
      cnum g1 = (fb[i] - conj(fb[j])) * r0;
      swap(g1.x, g1.y);
      g1.y *= -1;
      if (j != i) {
        swap(fa[j], fa[i]);
        fb[j] = fa[j] * g1;
        fa[j] = fa[j] * g0;
      }
      fb[i] = fa[i] * conj(g1);
      fa[i] = fa[i] * conj(g0);
    }
    fft<cnum>::go(fa.begin(), n);
    fft<cnum>::go(fb.begin(), n);
    using ll = long long;
    const ll m = mnum::MOD;
    auto it = io;
    for (int i = 0; i < s; ++i, ++it) {
      *it =
          mnum((ll(fa[i].x + 0.5) + (ll(fa[i].y + 0.5) % m << 15) +
                (ll(fb[i].x + 0.5) % m << 15) + (ll(fb[i].y + 0.5) % m << 30)) %
               m);
    }
  }
};
template <template <typename> class multiplier, typename T>
vector<T> multiply(const vector<T>& a, const vector<T>& b) {
  vector<T> r(max(0, sz(a) + sz(b) - 1));
  multiplier<T>::multiply(begin(a), sz(a), begin(b), sz(b), begin(r));
  return r;
}
template <template <typename> class inverser, typename T>
vector<T> inverse(const vector<T>& a) {
  vector<T> r(sz(a));
  inverser<T>::inverse(begin(a), sz(a), begin(r));
  return r;
}
}  // namespace fft
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int N, K;
  cin >> N >> K;
  using num = modnum<998244353>;
  int L = 1;
  while (L <= 9 * (N / 2)) L *= 2;
  vector<num> A(L);
  for (int i = 0; i < K; i++) {
    int d;
    cin >> d;
    A[d] = 1;
  }
  fft::fft<num>::go(A.begin(), L);
  num Linv = num(L).inv();
  for (int i = 0; i < L; i++) {
    A[i] = pow(A[i], N / 2);
    A[i] *= Linv;
  }
  reverse(A.begin() + 1, A.end());
  fft::fft<num>::go(A.begin(), L);
  num ans = 0;
  for (int i = 0; i <= 9 * (N / 2); i++) {
    ans += A[i] * A[i];
  }
  cout << ans << '\n';
  return 0;
}