#include <bits/stdc++.h>
static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;
template <class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
constexpr int ntt_mod = 998244353, ntt_root = 3;
template <u32 M = 1000000007>
struct modint {
  u32 val;
  modint() : val(0) {}
  template <typename T>
  modint(T t) {
    t %= (T)M;
    if (t < 0) t += (T)M;
    val = t;
  }
  modint pow(ll k) const {
    modint res(1), x(val);
    while (k) {
      if (k & 1) res *= x;
      x *= x;
      k >>= 1;
    }
    return res;
  }
  template <typename T>
  modint& operator=(T t) {
    t %= (T)M;
    if (t < 0) t += (T)M;
    val = t;
    return *this;
  }
  modint inv() const { return pow(M - 2); }
  modint& operator+=(modint a) {
    val += a.val;
    if (val >= M) val -= M;
    return *this;
  }
  modint& operator-=(modint a) {
    if (val < a.val)
      val += M - a.val;
    else
      val -= a.val;
    return *this;
  }
  modint& operator*=(modint a) {
    val = (u64)val * a.val % M;
    return *this;
  }
  modint& operator/=(modint a) { return (*this) *= a.inv(); }
  modint operator+(modint a) const { return modint(val) += a; }
  modint operator-(modint a) const { return modint(val) -= a; }
  modint operator*(modint a) const { return modint(val) *= a; }
  modint operator/(modint a) const { return modint(val) /= a; }
  modint operator-() { return modint(M - val); }
  bool operator==(const modint a) const { return val == a.val; }
  bool operator!=(const modint a) const { return val != a.val; }
  bool operator<(const modint a) const { return val < a.val; }
};
using mint = modint<ntt_mod>;
class NTT {
  static constexpr int max_base = 21, maxN = 1 << max_base;
  mint roots[maxN << 1], iroots[maxN << 1];

 public:
  NTT() {
    for (int i = 0; i <= max_base; ++i) {
      const int offset = (1 << i) - 1;
      const mint g = mint(ntt_root).pow((ntt_mod) / (1 << i)), ginv = g.inv();
      mint x = 1, y = 1;
      for (int j = 0; j < 1 << i; ++j) {
        roots[offset + j] = x;
        x *= g;
        iroots[offset + j] = y;
        y *= ginv;
      }
    }
  }
  void transform(vector<mint>& a, int sign) {
    const int n = a.size();
    if (!sign) {
      for (int k = n >> 1; k >= 1; k >>= 1) {
        for (int i = 0; i < n; i += k << 1) {
          for (int j = 0; j < k; ++j) {
            const mint tmp = a[i + j] - a[i + j + k];
            a[i + j] += a[i + j + k];
            a[i + j + k] = tmp * roots[(k << 1) - 1 + j];
          }
        }
      }
    } else {
      for (int k = 1; k <= (n >> 1); k <<= 1) {
        for (int i = 0; i < n; i += k << 1) {
          for (int j = 0; j < k; ++j) {
            a[i + j + k] *= iroots[(k << 1) - 1 + j];
            const mint tmp = a[i + j] - a[i + j + k];
            a[i + j] += a[i + j + k];
            a[i + j + k] = tmp;
          }
        }
      }
      const mint x = mint(n).inv();
      for (auto&& i : a) i *= x;
    }
  }
};
NTT ntt;
struct poly {
  vector<mint> v;
  poly() = default;
  explicit poly(int n) : v(n){};
  explicit poly(vector<mint> vv) : v(std::move(vv)){};
  int size() const { return (int)v.size(); }
  poly cut(int len) {
    if (len < v.size()) v.resize(static_cast<unsigned long>(len));
    return *this;
  }
  inline mint& operator[](int i) { return v[i]; }
  poly& operator+=(const poly& a) {
    this->v.resize(max(size(), a.size()));
    for (int i = 0; i < a.size(); ++i) this->v[i] += a.v[i];
    return *this;
  }
  poly& operator-=(const poly& a) {
    this->v.resize(max(size(), a.size()));
    for (int i = 0; i < a.size(); ++i) this->v[i] -= a.v[i];
    return *this;
  }
  poly& operator*=(poly a) {
    int N = size() + a.size() - 1;
    int sz = 1;
    while (sz < N) sz <<= 1;
    this->v.resize(sz);
    a.v.resize(sz);
    ntt.transform(this->v, 0);
    ntt.transform(a.v, 0);
    for (int i = 0; i < sz; ++i) this->v[i] *= a.v[i];
    ntt.transform(this->v, 1);
    this->v.resize(N);
    return *this;
  }
  poly& operator/=(const poly& a) { return (*this *= a.inv()); }
  poly operator+(const poly& a) const { return poly(*this) += a; }
  poly operator-(const poly& a) const { return poly(*this) -= a; }
  poly operator*(const poly& a) const { return poly(*this) *= a; }
  poly inv() const {
    int n = size();
    poly r(1);
    r[0] = (this->v[0]).inv();
    int k = 1;
    while (k < n) {
      k *= 2;
      poly ff(k);
      for (int i = 0; i < min(k, n); ++i) {
        ff[i] = this->v[i];
      }
      poly nr = (r * r * ff).cut(k);
      for (int i = 0; i < k / 2; ++i) {
        nr[i] = (r[i] + r[i] - nr[i]);
        nr[i + k / 2] = -nr[i + k / 2];
      }
      r = nr;
    }
    r.v.resize(n);
    return r;
  }
};
template <class T>
T pow_(T x, T n, T M) {
  uint64_t u = 1, xx = x;
  while (n > 0) {
    if (n & 1) u = u * xx % M;
    xx = xx * xx % M;
    n >>= 1;
  }
  return static_cast<T>(u);
};
int main() {
  int n, k;
  cin >> n >> k;
  n /= 2;
  vector<int> v(k);
  for (auto&& i : v) scanf("%d", &i);
  auto f = poly(*max_element(v.begin(), v.end()) + 1);
  for (int i = 0; i < k; ++i) {
    f[v[i]] += mint(1);
  }
  auto g = poly(1);
  g[0] = mint(1);
  while (n > 0) {
    if (n & 1) g *= f;
    f *= f;
    n >>= 1;
  }
  mint ans = 0;
  for (int i = 0; i < g.size(); ++i) {
    ans += g[i] * g[i];
  }
  cout << ans.val << "\n";
  return 0;
}

### Prompt

In CPP, your task is to solve 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>
static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;
template <class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
constexpr int ntt_mod = 998244353, ntt_root = 3;
template <u32 M = 1000000007>
struct modint {
  u32 val;
  modint() : val(0) {}
  template <typename T>
  modint(T t) {
    t %= (T)M;
    if (t < 0) t += (T)M;
    val = t;
  }
  modint pow(ll k) const {
    modint res(1), x(val);
    while (k) {
      if (k & 1) res *= x;
      x *= x;
      k >>= 1;
    }
    return res;
  }
  template <typename T>
  modint& operator=(T t) {
    t %= (T)M;
    if (t < 0) t += (T)M;
    val = t;
    return *this;
  }
  modint inv() const { return pow(M - 2); }
  modint& operator+=(modint a) {
    val += a.val;
    if (val >= M) val -= M;
    return *this;
  }
  modint& operator-=(modint a) {
    if (val < a.val)
      val += M - a.val;
    else
      val -= a.val;
    return *this;
  }
  modint& operator*=(modint a) {
    val = (u64)val * a.val % M;
    return *this;
  }
  modint& operator/=(modint a) { return (*this) *= a.inv(); }
  modint operator+(modint a) const { return modint(val) += a; }
  modint operator-(modint a) const { return modint(val) -= a; }
  modint operator*(modint a) const { return modint(val) *= a; }
  modint operator/(modint a) const { return modint(val) /= a; }
  modint operator-() { return modint(M - val); }
  bool operator==(const modint a) const { return val == a.val; }
  bool operator!=(const modint a) const { return val != a.val; }
  bool operator<(const modint a) const { return val < a.val; }
};
using mint = modint<ntt_mod>;
class NTT {
  static constexpr int max_base = 21, maxN = 1 << max_base;
  mint roots[maxN << 1], iroots[maxN << 1];

 public:
  NTT() {
    for (int i = 0; i <= max_base; ++i) {
      const int offset = (1 << i) - 1;
      const mint g = mint(ntt_root).pow((ntt_mod) / (1 << i)), ginv = g.inv();
      mint x = 1, y = 1;
      for (int j = 0; j < 1 << i; ++j) {
        roots[offset + j] = x;
        x *= g;
        iroots[offset + j] = y;
        y *= ginv;
      }
    }
  }
  void transform(vector<mint>& a, int sign) {
    const int n = a.size();
    if (!sign) {
      for (int k = n >> 1; k >= 1; k >>= 1) {
        for (int i = 0; i < n; i += k << 1) {
          for (int j = 0; j < k; ++j) {
            const mint tmp = a[i + j] - a[i + j + k];
            a[i + j] += a[i + j + k];
            a[i + j + k] = tmp * roots[(k << 1) - 1 + j];
          }
        }
      }
    } else {
      for (int k = 1; k <= (n >> 1); k <<= 1) {
        for (int i = 0; i < n; i += k << 1) {
          for (int j = 0; j < k; ++j) {
            a[i + j + k] *= iroots[(k << 1) - 1 + j];
            const mint tmp = a[i + j] - a[i + j + k];
            a[i + j] += a[i + j + k];
            a[i + j + k] = tmp;
          }
        }
      }
      const mint x = mint(n).inv();
      for (auto&& i : a) i *= x;
    }
  }
};
NTT ntt;
struct poly {
  vector<mint> v;
  poly() = default;
  explicit poly(int n) : v(n){};
  explicit poly(vector<mint> vv) : v(std::move(vv)){};
  int size() const { return (int)v.size(); }
  poly cut(int len) {
    if (len < v.size()) v.resize(static_cast<unsigned long>(len));
    return *this;
  }
  inline mint& operator[](int i) { return v[i]; }
  poly& operator+=(const poly& a) {
    this->v.resize(max(size(), a.size()));
    for (int i = 0; i < a.size(); ++i) this->v[i] += a.v[i];
    return *this;
  }
  poly& operator-=(const poly& a) {
    this->v.resize(max(size(), a.size()));
    for (int i = 0; i < a.size(); ++i) this->v[i] -= a.v[i];
    return *this;
  }
  poly& operator*=(poly a) {
    int N = size() + a.size() - 1;
    int sz = 1;
    while (sz < N) sz <<= 1;
    this->v.resize(sz);
    a.v.resize(sz);
    ntt.transform(this->v, 0);
    ntt.transform(a.v, 0);
    for (int i = 0; i < sz; ++i) this->v[i] *= a.v[i];
    ntt.transform(this->v, 1);
    this->v.resize(N);
    return *this;
  }
  poly& operator/=(const poly& a) { return (*this *= a.inv()); }
  poly operator+(const poly& a) const { return poly(*this) += a; }
  poly operator-(const poly& a) const { return poly(*this) -= a; }
  poly operator*(const poly& a) const { return poly(*this) *= a; }
  poly inv() const {
    int n = size();
    poly r(1);
    r[0] = (this->v[0]).inv();
    int k = 1;
    while (k < n) {
      k *= 2;
      poly ff(k);
      for (int i = 0; i < min(k, n); ++i) {
        ff[i] = this->v[i];
      }
      poly nr = (r * r * ff).cut(k);
      for (int i = 0; i < k / 2; ++i) {
        nr[i] = (r[i] + r[i] - nr[i]);
        nr[i + k / 2] = -nr[i + k / 2];
      }
      r = nr;
    }
    r.v.resize(n);
    return r;
  }
};
template <class T>
T pow_(T x, T n, T M) {
  uint64_t u = 1, xx = x;
  while (n > 0) {
    if (n & 1) u = u * xx % M;
    xx = xx * xx % M;
    n >>= 1;
  }
  return static_cast<T>(u);
};
int main() {
  int n, k;
  cin >> n >> k;
  n /= 2;
  vector<int> v(k);
  for (auto&& i : v) scanf("%d", &i);
  auto f = poly(*max_element(v.begin(), v.end()) + 1);
  for (int i = 0; i < k; ++i) {
    f[v[i]] += mint(1);
  }
  auto g = poly(1);
  g[0] = mint(1);
  while (n > 0) {
    if (n & 1) g *= f;
    f *= f;
    n >>= 1;
  }
  mint ans = 0;
  for (int i = 0; i < g.size(); ++i) {
    ans += g[i] * g[i];
  }
  cout << ans.val << "\n";
  return 0;
}

```