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;
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("");
}