#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 3000000;
int getin() {
  int x = 0, f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
  return x * f;
}
int qmod1(const int &x) { return x >= mod ? x - mod : x; }
int qmod2(const int &x) { return x + (x >> 31 & mod); }
int qpower(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
struct Z {
  int x;
  Z(int v = 0) { x = qmod2(v % mod); }
  int qmod1(const int &x) const { return x >= mod ? x - mod : x; }
  int qmod2(const int &x) const { return x + (x >> 31 & mod); }
  int qpower(int a, int b) const {
    int ans = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
      if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
  }
  Z &operator+=(const Z &b) {
    x += b.x;
    if (x >= mod) x -= mod;
    return *this;
  }
  Z &operator-=(const Z &b) {
    x -= b.x;
    x += x >> 31 & mod;
    return *this;
  }
  Z &operator*=(const Z &b) {
    x = 1ll * x * b.x % mod;
    return *this;
  }
  Z inv() const { return qpower(x, mod - 2); }
  Z &operator/=(const Z &b) {
    x = 1ll * x * qpower(b.x, mod - 2) % mod;
    return *this;
  }
  Z operator-() const { return (Z){qmod2(-x)}; }
  operator int() const { return x; }
};
Z operator+(const Z &a, const Z &b) { return (Z){qmod1(a.x + b.x)}; }
Z operator-(const Z &a, const Z &b) { return (Z){qmod2(a.x - b.x)}; }
Z operator*(const Z &a, const Z &b) {
  return (Z){(int)(1ll * a.x * b.x % mod)};
}
Z operator/(const Z &a, const Z &b) {
  return (Z){(int)(1ll * a.x * qpower(b.x, mod - 2) % mod)};
}
Z operator+(const Z &a, const int &b) { return a + Z(b); }
Z operator+(const int &a, const Z &b) { return (Z)a + b; }
Z operator-(const Z &a, const int &b) { return a - Z(b); }
Z operator-(const int &a, const Z &b) { return (Z)a - b; }
Z operator*(const Z &a, const int &b) { return a * Z(b); }
Z operator*(const int &a, const Z &b) { return Z(a) * b; }
Z operator/(const Z &a, const int &b) { return a * Z(b); }
Z operator/(const int &a, const Z &b) { return Z(a) * b; }
bool operator<(const Z &a, const Z &b) { return a.x < b.x; }
bool operator==(const Z &a, const Z &b) { return a.x == b.x; }
template <typename T>
T qpower(T a, int b) {
  T ans = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) ans = ans * a;
  return ans;
}
void print(const Z &a) { printf("%d", a.x); }
struct Zd {
  Z x, y, d;
  Zd(const Z &_x, const Z &_y, const Z &_d) { x = _x, y = _y, d = _d; }
  Zd(const Z &_x) { x = _x, y = 0; }
  Zd operator+(const Zd &a) const { return Zd(x + a.x, y + a.y, d); }
  Zd operator-(const Zd &a) const { return Zd(x - a.x, y - a.y, d); }
  Zd operator*(const Zd &a) const {
    return Zd(x * a.x + y * a.y * d, x * a.y + y * a.x, d);
  }
  Zd inv() const {
    Z t = x * x - y * y * d;
    t = t.inv();
    return Zd(x * t, -y * t, d);
  }
  Zd operator/(const Zd &a) const { return *this * a.inv(); }
  Zd &operator+=(const Zd &a) {
    x += a.x, y += a.y;
    return *this;
  }
  Zd &operator-=(const Zd &a) {
    x -= a.x, y -= a.y;
    return *this;
  }
  Zd &operator*=(const Zd &a) {
    *this = *this * a;
    return *this;
  }
  Zd &operator/=(const Zd &a) {
    *this = *this / a;
    return *this;
  }
  Zd operator-() const { return Zd(-x, -y, d); }
};
Zd qpower(Zd a, int b) {
  Zd ans(1, 0, a.d);
  for (; b; b >>= 1, a = a * a)
    if (b & 1) ans = ans * a;
  return ans;
}
Z sqrt(Z x) {
  Z a = rand(), t;
  while (qpower(t = a * a - x, (mod - 1) >> 1) == Z(1)) a = rand();
  Zd w(a, -1, t), ans = qpower(w, (mod + 1) >> 1);
  return min(ans.x, -ans.x);
}
namespace Poly_fast {
int w[N], inv[N], pool[N << 4];
int limn, rev[N], lg[N];
int curn;
void prework(int n) {
  limn = 1;
  while (limn < n) limn <<= 1;
  for (int i = 1; i < limn; i++)
    rev[i] = rev[i >> 1] >> 1 | ((i & 1) ? (limn >> 1) : 0);
  for (int i = 1; i < limn; i <<= 1) {
    w[i] = 1;
    int omg = qpower(3, (mod - 1) / (i << 1));
    for (int j = 1; j < i; j++) w[i + j] = 1ll * w[i + j - 1] * omg % mod;
  }
  for (int i = 2; i <= limn; i++) lg[i] = lg[i >> 1] + 1;
  inv[1] = 1;
  for (int i = 2; i < limn; i++)
    inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
}
void setn(int n) {
  curn = n;
  if (limn < n) prework(n);
}
void DFT(int a[], int n) {
  if (limn < n) prework(n);
  int t = lg[limn / n];
  unsigned long long tmp[n];
  for (int i = 0; i < n; i++) tmp[rev[i] >> t] = a[i];
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; k++) {
        unsigned t = tmp[i + j + k] * w[i + k] % mod;
        tmp[i + j + k] = tmp[j + k] + mod - t, tmp[j + k] += t;
      }
  for (int i = 0; i < n; i++) a[i] = tmp[i] % mod;
}
void IDFT(int a[], int n) {
  reverse(a + 1, a + n);
  DFT(a, n);
  int iv = mod - (mod - 1) / n;
  for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * iv % mod;
}
void print(int a[], int n) {
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  puts("");
}
void mul(const int A[], const int B[], int c[], const int &n) {
  int l = 1;
  while (l < (n << 1)) l <<= 1;
  int tmpa[l], tmpb[l];
  copy(A, A + n, tmpa), copy(B, B + n, tmpb);
  fill(tmpa + n, tmpa + l, 0), fill(tmpb + n, tmpb + l, 0);
  DFT(tmpa, l), DFT(tmpb, l);
  for (int i = 0; i < l; i++) c[i] = 1ll * tmpa[i] * tmpb[i] % mod;
  IDFT(c, l);
}
int *_f[20][1 << 3], *_g[20][1 << 3];
void cdq(const int l, const int r, int dep, int f[], const int g[],
         void brute(int *, const int *, const int, const int)) {
  if (r - l + 1 <= 32) {
    brute(f, g, l, r);
    return;
  }
  const int d = 1 << ((dep - 1) * 3);
  int tmpf[d << 1];
  for (int i = 0;; i++) {
    int L = l + i * d, R = min(r, L + d - 1);
    if (i) {
      fill(tmpf, tmpf + (d << 1), 0);
      for (int j = 0; j < i; j++)
        for (int k = 0; k < (d << 1); k++)
          tmpf[k] = (tmpf[k] + 1ll * _f[dep][j][k] * _g[dep][i - j][k]) % mod;
      IDFT(tmpf, d << 1);
      for (int i = L; i <= R; i++) f[i] = qmod1(f[i] + tmpf[i - L + d]);
    }
    cdq(L, R, dep - 1, f, g, brute);
    if (R == r) return;
    fill(_f[dep][i], _f[dep][i] + (d << 1), 0);
    copy(f + L, f + R + 1, _f[dep][i]);
    DFT(_f[dep][i], d << 1);
  }
}
void cdq_pre(int f[], const int g[], const int n,
             void brute(int *, const int *, const int, const int)) {
  fill(f, f + n, 0);
  if (n <= 128) {
    brute(f, g, 0, n - 1);
    return;
  }
  int len = 1, dep = 0;
  while (len < n) len <<= 3, ++dep;
  len >>= 3;
  int *p = pool;
  for (int i = 1; i <= dep; i++) {
    int d = 1 << ((i - 1) * 3), tn = min((1 << 3) - 1, (n - 1) / d);
    for (int j = 1; j <= tn; j++) {
      int l = (j - 1) * d + 1, r = min(n - 1, (j + 1) * d - 1);
      _f[i][j - 1] = p, p += d << 1;
      _g[i][j] = p;
      p += d << 1;
      fill(_g[i][j], _g[i][j] + (d << 1), 0);
      copy(g + l, g + r + 1, _g[i][j] + 1);
      DFT(_g[i][j], d << 1);
    }
  }
  cdq(0, n - 1, dep, f, g, brute);
}
void Der(int f[], const int g[], const int n) {
  for (int i = 0; i < n - 1; i++) f[i] = 1ll * (i + 1) * g[i + 1] % mod;
  f[n - 1] = 0;
}
void Int(int f[], const int g[], const int n) {
  for (int i = n - 1; i >= 1; i--) f[i] = 1ll * inv[i] * g[i - 1] % mod;
  f[0] = 0;
}
void brute_ln(int f[], const int g[], const int l, const int r) {
  if (!l)
    f[l] = 0;
  else
    f[l] = qmod2(1ll * l * g[l] % mod - f[l]);
  for (int i = l + 1; i <= r; i++) {
    for (int j = l; j < i; j++) f[i] = (f[i] + 1ll * f[j] * g[i - j]) % mod;
    f[i] = qmod2(1ll * i * g[i] % mod - f[i]);
  }
}
void Ln(int f[], const int g[], const int n) {
  cdq_pre(f, g, n, brute_ln);
  f[0] = 0;
  for (int i = 1; i < n; i++) f[i] = 1ll * f[i] * inv[i] % mod;
}
void brute_exp(int f[], const int g[], const int l, const int r) {
  if (!l)
    f[l] = 1;
  else
    f[l] = 1ll * f[l] * inv[l] % mod;
  for (int i = l + 1; i <= r; i++) {
    for (int j = l; j < i; j++) f[i] = (f[i] + 1ll * f[j] * g[i - j]) % mod;
    f[i] = 1ll * f[i] * inv[i] % mod;
  }
}
void Exp(int f[], const int g[], const int n) {
  int tmpg[n];
  for (int i = 0; i < n; i++) tmpg[i] = 1ll * i * g[i] % mod;
  cdq_pre(f, tmpg, n, brute_exp);
}
void brute_inv(int f[], const int g[], const int l, const int r) {
  if (!l) f[l] = 1;
  for (int i = l + 1; i <= r; i++)
    for (int j = l; j < i; j++) f[i] = (f[i] + 1ll * f[j] * g[i - j]) % mod;
}
void Inv(int f[], const int g[], const int n) {
  int tmpg[n];
  int iv = qpower(g[0], mod - 2);
  for (int i = 1; i < n; i++) tmpg[i] = 1ll * (mod - g[i]) * iv % mod;
  cdq_pre(f, tmpg, n, brute_inv);
  for (int i = 0; i < n; i++) f[i] = 1ll * f[i] * iv % mod;
}
void Pow(int f[], const int g[], const int n, const int K) {
  Ln(f, g, n);
  for (int i = 0; i < n; i++) f[i] = 1ll * f[i] * K % mod;
  int tmpf[n];
  copy(f, f + n, tmpf);
  Exp(f, tmpf, n);
}
void Sqrt(int f[], const int g[], const int n) {
  int t = g[0], iv = qpower(t, mod - 2);
  int tmpg[n];
  for (int i = 0; i < n; i++) tmpg[i] = 1ll * g[i] * iv % mod;
  Pow(f, tmpg, n, (mod + 1) >> 1);
  t = sqrt((Z)t);
  for (int i = 0; i < n; i++) f[i] = 1ll * f[i] * t % mod;
}
}  // namespace Poly_fast
struct Poly {
  vector<Z> a;
  Poly() {}
  Poly(const Z &x) {
    a.resize(1);
    a[0] = x;
  }
  Poly(const Z &x, const Z &y) {
    a.resize(2);
    a[0] = x, a[1] = y;
  }
  int size() const { return a.size(); }
  void resize(const int &x) { a.resize(x); }
  Z operator[](const int &x) const { return a[x]; }
  Z &operator[](const int &x) { return a[x]; }
  void init(const int &n) {
    a.resize(n);
    for (int i = 0; i < n; i++) a[i] = getin();
  }
  Poly &operator+=(const Poly &b) {
    int m = b.size();
    if ((int)a.size() < m) a.resize(m);
    for (int i = 0; i < m; i++) a[i] += b[i];
    return *this;
  }
  Poly operator-() const {
    Poly c;
    int n = a.size();
    c.resize(n);
    for (int i = 0; i < n; i++) c[i] = -a[i];
    return c;
  }
  Poly &operator-=(const Poly &b) {
    int m = b.size();
    if ((int)a.size() < m) a.resize(m);
    for (int i = 0; i < m; i++) a[i] -= b[i];
    return *this;
  }
  Poly &operator*=(const Poly &b) {
    using namespace Poly_fast;
    const int n = curn ? curn : a.size() + b.size() - 1;
    if (n <= 32 || a.size() < 5 || b.size() < 5) {
      Poly ans;
      ans.resize(n);
      for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < b.size() && i + j < n; j++)
          ans[i + j] += a[i] * b[j];
      *this = ans;
      return *this;
    }
    int l = 1;
    if (curn) {
      while (l < (n << 1)) l <<= 1;
    } else {
      while (l < n) l <<= 1;
    }
    const int len = l;
    int f[len], g[len];
    fill(f, f + l, 0), fill(g, g + l, 0);
    copy(a.begin(), min(a.begin() + n, a.end()), f),
        copy(b.a.begin(), min(b.a.begin() + n, b.a.end()), g);
    DFT(f, l), DFT(g, l);
    for (int i = 0; i < l; i++) f[i] = 1ll * f[i] * g[i] % mod;
    IDFT(f, l);
    a.resize(n);
    copy(f, f + n, a.begin());
    return *this;
  }
  Poly inv() const {
    using namespace Poly_fast;
    const int n = curn ? curn : a.size();
    int tmpg[n], tmpf[n];
    fill(tmpg, tmpg + n, 0);
    copy(a.begin(), min(a.begin() + n, a.end()), tmpg);
    Inv(tmpf, tmpg, n);
    Poly ans;
    ans.resize(n);
    copy(tmpf, tmpf + n, ans.a.begin());
    return ans;
  }
  Poly &operator/=(const Poly &b) {
    int n = a.size(), m = b.size();
    if (n < m) {
      return *this = Poly(0);
    }
    if (1ll * m * (n - m) <= 32 || m <= 4 || n - m <= 4) {
      Poly tmp = *this;
      a.resize(n - m + 1);
      for (int i = n - 1; i >= m - 1; i--) {
        Z t = tmp[i] / b[m - 1];
        a[i - m + 1] = t;
        for (int j = 0; j < m; j++) tmp[i - j] -= b[m - 1 - j] * t;
      }
      return *this;
    }
    Poly tmpb = b;
    using namespace Poly_fast;
    int tcurn = curn;
    reverse(a.begin(), a.end()), reverse(tmpb.a.begin(), tmpb.a.end());
    setn(n - m + 1);
    *this *= tmpb.inv();
    reverse(a.begin(), a.end());
    curn = tcurn;
    return *this;
  }
  Poly &operator%=(const Poly &b) {
    int n = a.size(), m = b.size();
    if (n < m) return *this;
    if (1ll * (n - m) * m <= 32 || n - m <= 4 || m <= 4) {
      for (int i = n - 1; i >= m - 1; i--) {
        Z t = a[i] / b[m - 1];
        for (int j = 0; j < m; j++) a[i - j] -= b[m - 1 - j] * t;
      }
      a.resize(m - 1);
      return *this;
    }
    using namespace Poly_fast;
    Poly tmpa = *this, tmpb = b;
    int tcurn = curn;
    reverse(tmpa.a.begin(), tmpa.a.end()),
        reverse(tmpb.a.begin(), tmpb.a.end());
    setn(n - m + 1);
    tmpa *= tmpb.inv();
    reverse(tmpa.a.begin(), tmpa.a.end());
    setn(m - 1);
    tmpa *= b;
    *this -= tmpa;
    curn = tcurn;
    return *this;
  }
};
Poly operator+(const Poly &a, const Poly &b) {
  Poly t = a;
  return t += b;
}
Poly operator-(const Poly &a, const Poly &b) {
  Poly t = a;
  return t -= b;
}
Poly operator*(const Poly &a, const Poly &b) {
  Poly t = a;
  return t *= b;
}
Poly operator/(const Poly &a, const Poly &b) {
  Poly t = a;
  return t /= b;
}
Poly operator%(const Poly &a, const Poly &b) {
  Poly t = a;
  return t %= b;
}
void print(const Poly &a) {
  for (int i = 0; i < a.size(); i++) print(a[i]), putchar(' ');
  puts("");
}
Poly qpower(const Poly &A, int b, const Poly &M) {
  using namespace Poly_fast;
  int tcurn = curn;
  setn(0);
  Poly ans(1);
  Poly a = A;
  for (; b; b >>= 1, a = a * a % M)
    if (b & 1) ans = ans * a % M;
  curn = tcurn;
  return ans;
}
Poly Der(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  Poly ans = g;
  ans.resize(n);
  for (int i = 0; i < n - 1; i++) ans[i] = ans[i + 1] * Z(i + 1);
  ans[n - 1] = 0;
  return ans;
}
Poly Int(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size() + 1;
  Poly ans = g;
  ans.resize(n);
  if (limn <= n) prework(n + 1);
  for (int i = n - 1; i >= 1; i--) ans[i] = ans[i - 1] * Z(inv[i]);
  ans[0] = 0;
  return ans;
}
Poly Inv(const Poly &g) { return g.inv(); }
Poly Ln(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Ln(tmpf, tmpg, n);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Exp(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Exp(tmpf, tmpg, n);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Pow(const Poly &g, const int &K) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Pow(tmpf, tmpg, n, K);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Sqrt(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Sqrt(tmpf, tmpg, n);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Newton(int tn, Poly calc(const Poly &), Z f0) {
  using namespace Poly_fast;
  Poly f(f0);
  for (int n = 1; n < tn; n <<= 1) {
    setn(n << 1);
    f -= calc(f);
  }
  f.resize(tn);
  setn(0);
  return f;
}
namespace Recursive {
void doublen(int a[], int b[], int l) {
  using namespace Poly_fast;
  copy(a, a + l, b);
  IDFT(b, l);
  for (int i = 0; i < l; i++) b[i] = 1ll * b[i] * w[l + i] % mod;
  DFT(b, l);
  for (int i = l - 1; i >= 0; i--) b[i << 1 | 1] = b[i];
  for (int i = 0; i < l; i++) b[i << 1] = a[i];
}
int Liner(Poly Q, Poly a0, long long n) {
  using namespace Poly_fast;
  int K = Q.size();
  int l = 1;
  while (l <= K) l <<= 1;
  const int len = l << 1;
  int p[len], q[len], tmpp[len], tmpq[len];
  for (int i = 1; i <= K; i++) q[i] = -Q[i - 1];
  q[0] = 1;
  for (int i = 0; i < K; i++) p[i] = a0[i];
  mul(p, q, p, K);
  copy(p, p + K, tmpp), fill(tmpp + K, tmpp + (l << 1), 0);
  copy(q, q + K + 1, tmpq), fill(tmpq + K + 1, tmpq + (l << 1), 0);
  int iw[len >> 1];
  int omg = qpower(qpower(3, (mod - 1) / (l << 1)), mod - 2);
  iw[0] = 1;
  for (int i = 1; i < l; i++) iw[i] = 1ll * iw[i - 1] * omg % mod;
  int is_first = 1;
  while (n >= K) {
    if (is_first) {
      is_first = 0;
      DFT(tmpp, l << 1), DFT(tmpq, l << 1);
    } else {
      doublen(p, tmpp, l), doublen(q, tmpq, l);
    }
    if (n & 1) {
      int iv2 = (mod + 1) >> 1;
      for (int i = 0; i < l; i++)
        p[i] = (1ll * tmpp[i] * tmpq[i ^ l] +
                1ll * (mod - tmpp[i ^ l]) * tmpq[i]) %
               mod * iw[i] % mod * iv2 % mod;
    } else {
      int iv2 = (mod + 1) >> 1;
      for (int i = 0; i < l; i++)
        p[i] = (1ll * tmpp[i] * tmpq[i ^ l] + 1ll * tmpq[i] * tmpp[i ^ l]) %
               mod * iv2 % mod;
    }
    for (int i = 0; i < l; i++) q[i] = 1ll * tmpq[i] * tmpq[i ^ l] % mod;
    n >>= 1;
  }
  if (!is_first) {
    IDFT(p, l), IDFT(q, l);
  }
  Inv(q, q, K);
  mul(p, q, p, K);
  return p[n];
}
Poly BM(Poly f) {
  Poly ans, tans;
  int tfail = 0;
  Z delta, tdelta = 0;
  for (int i = 0; i < f.size(); i++) {
    delta = f[i];
    for (int j = 0; j < ans.size(); j++) delta += -ans[j] * f[i - j - 1];
    if (delta == Z(0)) continue;
    if (!ans.size()) {
      tfail = i;
      tdelta = delta;
      ans.resize(i + 1);
      continue;
    }
    Poly tmp = ans;
    if (ans.size() < i - tfail + tans.size())
      ans.resize(i - tfail + tans.size());
    Z t = delta / tdelta;
    ans[i - tfail - 1] = qmod1(ans[i - tfail - 1] + t);
    for (int j = 0; j < tans.size(); j++) ans[i - tfail + j] += -t * tans[j];
    if (tmp.size() - i < tans.size() - tfail) {
      tfail = i, tdelta = delta, tans = tmp;
    }
  }
  return ans;
}
}  // namespace Recursive
int n, tmp[20];
int main() {
  int n = getin() / 2, K = getin();
  Poly f;
  f.resize(10);
  for (int i = 1; i <= K; i++) tmp[i] = getin();
  int mi = 10;
  for (int i = 1; i <= K; i++) mi = min(mi, tmp[i]);
  for (int i = 1; i <= K; i++) tmp[i] -= mi;
  for (int i = 1; i <= K; i++) f[tmp[i]] = 1;
  Poly_fast::setn(n * 9 + 1);
  f = Pow(f, n);
  Z ans = 0;
  for (int i = 0; i <= n * 9; i++) ans += f[i] * f[i];
  print(ans);
  puts("");
}

### Prompt

Create a solution in CPP for the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 3000000;
int getin() {
  int x = 0, f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
  return x * f;
}
int qmod1(const int &x) { return x >= mod ? x - mod : x; }
int qmod2(const int &x) { return x + (x >> 31 & mod); }
int qpower(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
struct Z {
  int x;
  Z(int v = 0) { x = qmod2(v % mod); }
  int qmod1(const int &x) const { return x >= mod ? x - mod : x; }
  int qmod2(const int &x) const { return x + (x >> 31 & mod); }
  int qpower(int a, int b) const {
    int ans = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
      if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
  }
  Z &operator+=(const Z &b) {
    x += b.x;
    if (x >= mod) x -= mod;
    return *this;
  }
  Z &operator-=(const Z &b) {
    x -= b.x;
    x += x >> 31 & mod;
    return *this;
  }
  Z &operator*=(const Z &b) {
    x = 1ll * x * b.x % mod;
    return *this;
  }
  Z inv() const { return qpower(x, mod - 2); }
  Z &operator/=(const Z &b) {
    x = 1ll * x * qpower(b.x, mod - 2) % mod;
    return *this;
  }
  Z operator-() const { return (Z){qmod2(-x)}; }
  operator int() const { return x; }
};
Z operator+(const Z &a, const Z &b) { return (Z){qmod1(a.x + b.x)}; }
Z operator-(const Z &a, const Z &b) { return (Z){qmod2(a.x - b.x)}; }
Z operator*(const Z &a, const Z &b) {
  return (Z){(int)(1ll * a.x * b.x % mod)};
}
Z operator/(const Z &a, const Z &b) {
  return (Z){(int)(1ll * a.x * qpower(b.x, mod - 2) % mod)};
}
Z operator+(const Z &a, const int &b) { return a + Z(b); }
Z operator+(const int &a, const Z &b) { return (Z)a + b; }
Z operator-(const Z &a, const int &b) { return a - Z(b); }
Z operator-(const int &a, const Z &b) { return (Z)a - b; }
Z operator*(const Z &a, const int &b) { return a * Z(b); }
Z operator*(const int &a, const Z &b) { return Z(a) * b; }
Z operator/(const Z &a, const int &b) { return a * Z(b); }
Z operator/(const int &a, const Z &b) { return Z(a) * b; }
bool operator<(const Z &a, const Z &b) { return a.x < b.x; }
bool operator==(const Z &a, const Z &b) { return a.x == b.x; }
template <typename T>
T qpower(T a, int b) {
  T ans = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) ans = ans * a;
  return ans;
}
void print(const Z &a) { printf("%d", a.x); }
struct Zd {
  Z x, y, d;
  Zd(const Z &_x, const Z &_y, const Z &_d) { x = _x, y = _y, d = _d; }
  Zd(const Z &_x) { x = _x, y = 0; }
  Zd operator+(const Zd &a) const { return Zd(x + a.x, y + a.y, d); }
  Zd operator-(const Zd &a) const { return Zd(x - a.x, y - a.y, d); }
  Zd operator*(const Zd &a) const {
    return Zd(x * a.x + y * a.y * d, x * a.y + y * a.x, d);
  }
  Zd inv() const {
    Z t = x * x - y * y * d;
    t = t.inv();
    return Zd(x * t, -y * t, d);
  }
  Zd operator/(const Zd &a) const { return *this * a.inv(); }
  Zd &operator+=(const Zd &a) {
    x += a.x, y += a.y;
    return *this;
  }
  Zd &operator-=(const Zd &a) {
    x -= a.x, y -= a.y;
    return *this;
  }
  Zd &operator*=(const Zd &a) {
    *this = *this * a;
    return *this;
  }
  Zd &operator/=(const Zd &a) {
    *this = *this / a;
    return *this;
  }
  Zd operator-() const { return Zd(-x, -y, d); }
};
Zd qpower(Zd a, int b) {
  Zd ans(1, 0, a.d);
  for (; b; b >>= 1, a = a * a)
    if (b & 1) ans = ans * a;
  return ans;
}
Z sqrt(Z x) {
  Z a = rand(), t;
  while (qpower(t = a * a - x, (mod - 1) >> 1) == Z(1)) a = rand();
  Zd w(a, -1, t), ans = qpower(w, (mod + 1) >> 1);
  return min(ans.x, -ans.x);
}
namespace Poly_fast {
int w[N], inv[N], pool[N << 4];
int limn, rev[N], lg[N];
int curn;
void prework(int n) {
  limn = 1;
  while (limn < n) limn <<= 1;
  for (int i = 1; i < limn; i++)
    rev[i] = rev[i >> 1] >> 1 | ((i & 1) ? (limn >> 1) : 0);
  for (int i = 1; i < limn; i <<= 1) {
    w[i] = 1;
    int omg = qpower(3, (mod - 1) / (i << 1));
    for (int j = 1; j < i; j++) w[i + j] = 1ll * w[i + j - 1] * omg % mod;
  }
  for (int i = 2; i <= limn; i++) lg[i] = lg[i >> 1] + 1;
  inv[1] = 1;
  for (int i = 2; i < limn; i++)
    inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
}
void setn(int n) {
  curn = n;
  if (limn < n) prework(n);
}
void DFT(int a[], int n) {
  if (limn < n) prework(n);
  int t = lg[limn / n];
  unsigned long long tmp[n];
  for (int i = 0; i < n; i++) tmp[rev[i] >> t] = a[i];
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; k++) {
        unsigned t = tmp[i + j + k] * w[i + k] % mod;
        tmp[i + j + k] = tmp[j + k] + mod - t, tmp[j + k] += t;
      }
  for (int i = 0; i < n; i++) a[i] = tmp[i] % mod;
}
void IDFT(int a[], int n) {
  reverse(a + 1, a + n);
  DFT(a, n);
  int iv = mod - (mod - 1) / n;
  for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * iv % mod;
}
void print(int a[], int n) {
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  puts("");
}
void mul(const int A[], const int B[], int c[], const int &n) {
  int l = 1;
  while (l < (n << 1)) l <<= 1;
  int tmpa[l], tmpb[l];
  copy(A, A + n, tmpa), copy(B, B + n, tmpb);
  fill(tmpa + n, tmpa + l, 0), fill(tmpb + n, tmpb + l, 0);
  DFT(tmpa, l), DFT(tmpb, l);
  for (int i = 0; i < l; i++) c[i] = 1ll * tmpa[i] * tmpb[i] % mod;
  IDFT(c, l);
}
int *_f[20][1 << 3], *_g[20][1 << 3];
void cdq(const int l, const int r, int dep, int f[], const int g[],
         void brute(int *, const int *, const int, const int)) {
  if (r - l + 1 <= 32) {
    brute(f, g, l, r);
    return;
  }
  const int d = 1 << ((dep - 1) * 3);
  int tmpf[d << 1];
  for (int i = 0;; i++) {
    int L = l + i * d, R = min(r, L + d - 1);
    if (i) {
      fill(tmpf, tmpf + (d << 1), 0);
      for (int j = 0; j < i; j++)
        for (int k = 0; k < (d << 1); k++)
          tmpf[k] = (tmpf[k] + 1ll * _f[dep][j][k] * _g[dep][i - j][k]) % mod;
      IDFT(tmpf, d << 1);
      for (int i = L; i <= R; i++) f[i] = qmod1(f[i] + tmpf[i - L + d]);
    }
    cdq(L, R, dep - 1, f, g, brute);
    if (R == r) return;
    fill(_f[dep][i], _f[dep][i] + (d << 1), 0);
    copy(f + L, f + R + 1, _f[dep][i]);
    DFT(_f[dep][i], d << 1);
  }
}
void cdq_pre(int f[], const int g[], const int n,
             void brute(int *, const int *, const int, const int)) {
  fill(f, f + n, 0);
  if (n <= 128) {
    brute(f, g, 0, n - 1);
    return;
  }
  int len = 1, dep = 0;
  while (len < n) len <<= 3, ++dep;
  len >>= 3;
  int *p = pool;
  for (int i = 1; i <= dep; i++) {
    int d = 1 << ((i - 1) * 3), tn = min((1 << 3) - 1, (n - 1) / d);
    for (int j = 1; j <= tn; j++) {
      int l = (j - 1) * d + 1, r = min(n - 1, (j + 1) * d - 1);
      _f[i][j - 1] = p, p += d << 1;
      _g[i][j] = p;
      p += d << 1;
      fill(_g[i][j], _g[i][j] + (d << 1), 0);
      copy(g + l, g + r + 1, _g[i][j] + 1);
      DFT(_g[i][j], d << 1);
    }
  }
  cdq(0, n - 1, dep, f, g, brute);
}
void Der(int f[], const int g[], const int n) {
  for (int i = 0; i < n - 1; i++) f[i] = 1ll * (i + 1) * g[i + 1] % mod;
  f[n - 1] = 0;
}
void Int(int f[], const int g[], const int n) {
  for (int i = n - 1; i >= 1; i--) f[i] = 1ll * inv[i] * g[i - 1] % mod;
  f[0] = 0;
}
void brute_ln(int f[], const int g[], const int l, const int r) {
  if (!l)
    f[l] = 0;
  else
    f[l] = qmod2(1ll * l * g[l] % mod - f[l]);
  for (int i = l + 1; i <= r; i++) {
    for (int j = l; j < i; j++) f[i] = (f[i] + 1ll * f[j] * g[i - j]) % mod;
    f[i] = qmod2(1ll * i * g[i] % mod - f[i]);
  }
}
void Ln(int f[], const int g[], const int n) {
  cdq_pre(f, g, n, brute_ln);
  f[0] = 0;
  for (int i = 1; i < n; i++) f[i] = 1ll * f[i] * inv[i] % mod;
}
void brute_exp(int f[], const int g[], const int l, const int r) {
  if (!l)
    f[l] = 1;
  else
    f[l] = 1ll * f[l] * inv[l] % mod;
  for (int i = l + 1; i <= r; i++) {
    for (int j = l; j < i; j++) f[i] = (f[i] + 1ll * f[j] * g[i - j]) % mod;
    f[i] = 1ll * f[i] * inv[i] % mod;
  }
}
void Exp(int f[], const int g[], const int n) {
  int tmpg[n];
  for (int i = 0; i < n; i++) tmpg[i] = 1ll * i * g[i] % mod;
  cdq_pre(f, tmpg, n, brute_exp);
}
void brute_inv(int f[], const int g[], const int l, const int r) {
  if (!l) f[l] = 1;
  for (int i = l + 1; i <= r; i++)
    for (int j = l; j < i; j++) f[i] = (f[i] + 1ll * f[j] * g[i - j]) % mod;
}
void Inv(int f[], const int g[], const int n) {
  int tmpg[n];
  int iv = qpower(g[0], mod - 2);
  for (int i = 1; i < n; i++) tmpg[i] = 1ll * (mod - g[i]) * iv % mod;
  cdq_pre(f, tmpg, n, brute_inv);
  for (int i = 0; i < n; i++) f[i] = 1ll * f[i] * iv % mod;
}
void Pow(int f[], const int g[], const int n, const int K) {
  Ln(f, g, n);
  for (int i = 0; i < n; i++) f[i] = 1ll * f[i] * K % mod;
  int tmpf[n];
  copy(f, f + n, tmpf);
  Exp(f, tmpf, n);
}
void Sqrt(int f[], const int g[], const int n) {
  int t = g[0], iv = qpower(t, mod - 2);
  int tmpg[n];
  for (int i = 0; i < n; i++) tmpg[i] = 1ll * g[i] * iv % mod;
  Pow(f, tmpg, n, (mod + 1) >> 1);
  t = sqrt((Z)t);
  for (int i = 0; i < n; i++) f[i] = 1ll * f[i] * t % mod;
}
}  // namespace Poly_fast
struct Poly {
  vector<Z> a;
  Poly() {}
  Poly(const Z &x) {
    a.resize(1);
    a[0] = x;
  }
  Poly(const Z &x, const Z &y) {
    a.resize(2);
    a[0] = x, a[1] = y;
  }
  int size() const { return a.size(); }
  void resize(const int &x) { a.resize(x); }
  Z operator[](const int &x) const { return a[x]; }
  Z &operator[](const int &x) { return a[x]; }
  void init(const int &n) {
    a.resize(n);
    for (int i = 0; i < n; i++) a[i] = getin();
  }
  Poly &operator+=(const Poly &b) {
    int m = b.size();
    if ((int)a.size() < m) a.resize(m);
    for (int i = 0; i < m; i++) a[i] += b[i];
    return *this;
  }
  Poly operator-() const {
    Poly c;
    int n = a.size();
    c.resize(n);
    for (int i = 0; i < n; i++) c[i] = -a[i];
    return c;
  }
  Poly &operator-=(const Poly &b) {
    int m = b.size();
    if ((int)a.size() < m) a.resize(m);
    for (int i = 0; i < m; i++) a[i] -= b[i];
    return *this;
  }
  Poly &operator*=(const Poly &b) {
    using namespace Poly_fast;
    const int n = curn ? curn : a.size() + b.size() - 1;
    if (n <= 32 || a.size() < 5 || b.size() < 5) {
      Poly ans;
      ans.resize(n);
      for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < b.size() && i + j < n; j++)
          ans[i + j] += a[i] * b[j];
      *this = ans;
      return *this;
    }
    int l = 1;
    if (curn) {
      while (l < (n << 1)) l <<= 1;
    } else {
      while (l < n) l <<= 1;
    }
    const int len = l;
    int f[len], g[len];
    fill(f, f + l, 0), fill(g, g + l, 0);
    copy(a.begin(), min(a.begin() + n, a.end()), f),
        copy(b.a.begin(), min(b.a.begin() + n, b.a.end()), g);
    DFT(f, l), DFT(g, l);
    for (int i = 0; i < l; i++) f[i] = 1ll * f[i] * g[i] % mod;
    IDFT(f, l);
    a.resize(n);
    copy(f, f + n, a.begin());
    return *this;
  }
  Poly inv() const {
    using namespace Poly_fast;
    const int n = curn ? curn : a.size();
    int tmpg[n], tmpf[n];
    fill(tmpg, tmpg + n, 0);
    copy(a.begin(), min(a.begin() + n, a.end()), tmpg);
    Inv(tmpf, tmpg, n);
    Poly ans;
    ans.resize(n);
    copy(tmpf, tmpf + n, ans.a.begin());
    return ans;
  }
  Poly &operator/=(const Poly &b) {
    int n = a.size(), m = b.size();
    if (n < m) {
      return *this = Poly(0);
    }
    if (1ll * m * (n - m) <= 32 || m <= 4 || n - m <= 4) {
      Poly tmp = *this;
      a.resize(n - m + 1);
      for (int i = n - 1; i >= m - 1; i--) {
        Z t = tmp[i] / b[m - 1];
        a[i - m + 1] = t;
        for (int j = 0; j < m; j++) tmp[i - j] -= b[m - 1 - j] * t;
      }
      return *this;
    }
    Poly tmpb = b;
    using namespace Poly_fast;
    int tcurn = curn;
    reverse(a.begin(), a.end()), reverse(tmpb.a.begin(), tmpb.a.end());
    setn(n - m + 1);
    *this *= tmpb.inv();
    reverse(a.begin(), a.end());
    curn = tcurn;
    return *this;
  }
  Poly &operator%=(const Poly &b) {
    int n = a.size(), m = b.size();
    if (n < m) return *this;
    if (1ll * (n - m) * m <= 32 || n - m <= 4 || m <= 4) {
      for (int i = n - 1; i >= m - 1; i--) {
        Z t = a[i] / b[m - 1];
        for (int j = 0; j < m; j++) a[i - j] -= b[m - 1 - j] * t;
      }
      a.resize(m - 1);
      return *this;
    }
    using namespace Poly_fast;
    Poly tmpa = *this, tmpb = b;
    int tcurn = curn;
    reverse(tmpa.a.begin(), tmpa.a.end()),
        reverse(tmpb.a.begin(), tmpb.a.end());
    setn(n - m + 1);
    tmpa *= tmpb.inv();
    reverse(tmpa.a.begin(), tmpa.a.end());
    setn(m - 1);
    tmpa *= b;
    *this -= tmpa;
    curn = tcurn;
    return *this;
  }
};
Poly operator+(const Poly &a, const Poly &b) {
  Poly t = a;
  return t += b;
}
Poly operator-(const Poly &a, const Poly &b) {
  Poly t = a;
  return t -= b;
}
Poly operator*(const Poly &a, const Poly &b) {
  Poly t = a;
  return t *= b;
}
Poly operator/(const Poly &a, const Poly &b) {
  Poly t = a;
  return t /= b;
}
Poly operator%(const Poly &a, const Poly &b) {
  Poly t = a;
  return t %= b;
}
void print(const Poly &a) {
  for (int i = 0; i < a.size(); i++) print(a[i]), putchar(' ');
  puts("");
}
Poly qpower(const Poly &A, int b, const Poly &M) {
  using namespace Poly_fast;
  int tcurn = curn;
  setn(0);
  Poly ans(1);
  Poly a = A;
  for (; b; b >>= 1, a = a * a % M)
    if (b & 1) ans = ans * a % M;
  curn = tcurn;
  return ans;
}
Poly Der(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  Poly ans = g;
  ans.resize(n);
  for (int i = 0; i < n - 1; i++) ans[i] = ans[i + 1] * Z(i + 1);
  ans[n - 1] = 0;
  return ans;
}
Poly Int(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size() + 1;
  Poly ans = g;
  ans.resize(n);
  if (limn <= n) prework(n + 1);
  for (int i = n - 1; i >= 1; i--) ans[i] = ans[i - 1] * Z(inv[i]);
  ans[0] = 0;
  return ans;
}
Poly Inv(const Poly &g) { return g.inv(); }
Poly Ln(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Ln(tmpf, tmpg, n);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Exp(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Exp(tmpf, tmpg, n);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Pow(const Poly &g, const int &K) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Pow(tmpf, tmpg, n, K);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Sqrt(const Poly &g) {
  using namespace Poly_fast;
  const int n = curn ? curn : g.size();
  int tmpg[n], tmpf[n];
  fill(tmpg, tmpg + n, 0);
  copy(g.a.begin(), min(g.a.begin() + n, g.a.end()), tmpg);
  Sqrt(tmpf, tmpg, n);
  Poly ans;
  ans.resize(n);
  copy(tmpf, tmpf + n, ans.a.begin());
  return ans;
}
Poly Newton(int tn, Poly calc(const Poly &), Z f0) {
  using namespace Poly_fast;
  Poly f(f0);
  for (int n = 1; n < tn; n <<= 1) {
    setn(n << 1);
    f -= calc(f);
  }
  f.resize(tn);
  setn(0);
  return f;
}
namespace Recursive {
void doublen(int a[], int b[], int l) {
  using namespace Poly_fast;
  copy(a, a + l, b);
  IDFT(b, l);
  for (int i = 0; i < l; i++) b[i] = 1ll * b[i] * w[l + i] % mod;
  DFT(b, l);
  for (int i = l - 1; i >= 0; i--) b[i << 1 | 1] = b[i];
  for (int i = 0; i < l; i++) b[i << 1] = a[i];
}
int Liner(Poly Q, Poly a0, long long n) {
  using namespace Poly_fast;
  int K = Q.size();
  int l = 1;
  while (l <= K) l <<= 1;
  const int len = l << 1;
  int p[len], q[len], tmpp[len], tmpq[len];
  for (int i = 1; i <= K; i++) q[i] = -Q[i - 1];
  q[0] = 1;
  for (int i = 0; i < K; i++) p[i] = a0[i];
  mul(p, q, p, K);
  copy(p, p + K, tmpp), fill(tmpp + K, tmpp + (l << 1), 0);
  copy(q, q + K + 1, tmpq), fill(tmpq + K + 1, tmpq + (l << 1), 0);
  int iw[len >> 1];
  int omg = qpower(qpower(3, (mod - 1) / (l << 1)), mod - 2);
  iw[0] = 1;
  for (int i = 1; i < l; i++) iw[i] = 1ll * iw[i - 1] * omg % mod;
  int is_first = 1;
  while (n >= K) {
    if (is_first) {
      is_first = 0;
      DFT(tmpp, l << 1), DFT(tmpq, l << 1);
    } else {
      doublen(p, tmpp, l), doublen(q, tmpq, l);
    }
    if (n & 1) {
      int iv2 = (mod + 1) >> 1;
      for (int i = 0; i < l; i++)
        p[i] = (1ll * tmpp[i] * tmpq[i ^ l] +
                1ll * (mod - tmpp[i ^ l]) * tmpq[i]) %
               mod * iw[i] % mod * iv2 % mod;
    } else {
      int iv2 = (mod + 1) >> 1;
      for (int i = 0; i < l; i++)
        p[i] = (1ll * tmpp[i] * tmpq[i ^ l] + 1ll * tmpq[i] * tmpp[i ^ l]) %
               mod * iv2 % mod;
    }
    for (int i = 0; i < l; i++) q[i] = 1ll * tmpq[i] * tmpq[i ^ l] % mod;
    n >>= 1;
  }
  if (!is_first) {
    IDFT(p, l), IDFT(q, l);
  }
  Inv(q, q, K);
  mul(p, q, p, K);
  return p[n];
}
Poly BM(Poly f) {
  Poly ans, tans;
  int tfail = 0;
  Z delta, tdelta = 0;
  for (int i = 0; i < f.size(); i++) {
    delta = f[i];
    for (int j = 0; j < ans.size(); j++) delta += -ans[j] * f[i - j - 1];
    if (delta == Z(0)) continue;
    if (!ans.size()) {
      tfail = i;
      tdelta = delta;
      ans.resize(i + 1);
      continue;
    }
    Poly tmp = ans;
    if (ans.size() < i - tfail + tans.size())
      ans.resize(i - tfail + tans.size());
    Z t = delta / tdelta;
    ans[i - tfail - 1] = qmod1(ans[i - tfail - 1] + t);
    for (int j = 0; j < tans.size(); j++) ans[i - tfail + j] += -t * tans[j];
    if (tmp.size() - i < tans.size() - tfail) {
      tfail = i, tdelta = delta, tans = tmp;
    }
  }
  return ans;
}
}  // namespace Recursive
int n, tmp[20];
int main() {
  int n = getin() / 2, K = getin();
  Poly f;
  f.resize(10);
  for (int i = 1; i <= K; i++) tmp[i] = getin();
  int mi = 10;
  for (int i = 1; i <= K; i++) mi = min(mi, tmp[i]);
  for (int i = 1; i <= K; i++) tmp[i] -= mi;
  for (int i = 1; i <= K; i++) f[tmp[i]] = 1;
  Poly_fast::setn(n * 9 + 1);
  f = Pow(f, n);
  Z ans = 0;
  for (int i = 0; i <= n * 9; i++) ans += f[i] * f[i];
  print(ans);
  puts("");
}

```