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;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
struct GenericComplex {
  T a, b;
  GenericComplex() {
    a = T();
    b = T();
  }
  GenericComplex(T x) {
    a = x;
    b = T();
  }
  GenericComplex(T a, T b) : a(a), b(b) {}
  GenericComplex(const GenericComplex& rhs) {
    a = rhs.a;
    b = rhs.b;
  }
  inline T norm() const { return hypot(a, b); }
  inline GenericComplex conj() const { return {a, -b}; }
  static GenericComplex<T> nth_root(const int n) {
    const T pi = acos(T(-1));
    const T t = 2 * pi / n;
    GenericComplex<T> root;
    root.a = cos(t);
    root.b = sin(t);
    return root;
  }
  static vector<vector<GenericComplex<T>>> roots;
  static vector<vector<GenericComplex<T>>> roots_inv;
  static void ensure_roots(const size_t new_size) {
    if (roots.empty()) {
      roots.reserve(32);
      roots_inv.reserve(32);
      roots.push_back({});
      roots_inv.push_back({});
      roots.push_back({1});
      roots_inv.push_back({1});
    }
    const size_t previous_size = 2 * roots.back().size();
    if (new_size > previous_size) {
      for (size_t size = 2 * previous_size; size <= new_size; size *= 2) {
        roots.push_back({});
        roots_inv.push_back({});
        roots.back().resize(size / 2);
        roots_inv.back().resize(size / 2);
      }
      auto& roots_back = roots.back();
      auto& roots_inv_back = roots_inv.back();
      const T two_pi = 2 * acos(T(-1));
      const size_t half_new_size = new_size / 2;
      const size_t period = min<size_t>(half_new_size, 8);
      for (size_t i = 0; i < period; ++i) {
        const T angle = two_pi / new_size * i;
        roots_back[i].a = cos(angle);
        roots_back[i].b = sin(angle);
        roots_inv_back[i].a = roots_back[i].a;
        roots_inv_back[i].b = -roots_back[i].b;
      }
      for (size_t i = period; i < half_new_size; i += period) {
        const T angle = two_pi / new_size * i;
        roots_back[i].a = cos(angle);
        roots_back[i].b = sin(angle);
        roots_inv_back[i].a = roots_back[i].a;
        roots_inv_back[i].b = -roots_back[i].b;
        for (size_t j = 1; j < period; ++j) {
          roots_back[i + j] = roots_back[i] * roots_back[j];
          roots_inv_back[i + j].a = roots_back[i + j].a;
          roots_inv_back[i + j].b = -roots_back[i + j].b;
        }
      }
      size_t idx = roots.size() - 1;
      for (size_t size = new_size / 2; size > previous_size; size /= 2) {
        idx -= 1;
        for (size_t i = 0, j = 0; j < size; i += 1, j += 2) {
          roots[idx][i] = roots[idx + 1][j];
          roots_inv[idx][i] = roots_inv[idx + 1][j];
        }
      }
    }
  }
};
template <typename T>
vector<vector<GenericComplex<T>>> GenericComplex<T>::roots;
template <typename T>
vector<vector<GenericComplex<T>>> GenericComplex<T>::roots_inv;
template <typename T>
inline GenericComplex<T>& operator+=(GenericComplex<T>& lhs,
                                     const GenericComplex<T>& rhs) {
  lhs.a += rhs.a;
  lhs.b += rhs.b;
  return lhs;
};
template <typename T>
inline GenericComplex<T> operator+(GenericComplex<T> lhs,
                                   const GenericComplex<T>& rhs) {
  return lhs += rhs;
}
template <typename T>
inline GenericComplex<T>& operator-=(GenericComplex<T>& lhs,
                                     const GenericComplex<T>& rhs) {
  lhs.a -= rhs.a;
  lhs.b -= rhs.b;
  return lhs;
};
template <typename T>
inline GenericComplex<T> operator-(GenericComplex<T> lhs,
                                   const GenericComplex<T>& rhs) {
  return lhs -= rhs;
}
template <typename T>
inline GenericComplex<T>& operator*=(GenericComplex<T>& lhs,
                                     const GenericComplex<T>& rhs) {
  GenericComplex<T> old_lhs(lhs);
  lhs.a = old_lhs.a * rhs.a - old_lhs.b * rhs.b;
  lhs.b = old_lhs.b * rhs.a + old_lhs.a * rhs.b;
  return lhs;
}
template <typename T>
inline GenericComplex<T> operator*(const GenericComplex<T>& lhs,
                                   const GenericComplex<T>& rhs) {
  return GenericComplex<T>(lhs.a * rhs.a - lhs.b * rhs.b,
                           lhs.b * rhs.a + lhs.a * rhs.b);
}
template <typename T>
inline GenericComplex<T>& operator/=(GenericComplex<T>& lhs,
                                     const GenericComplex<T>& rhs) {
  GenericComplex<T> old_lhs(lhs);
  lhs.a = old_lhs.a * rhs.a + old_lhs.b * rhs.b;
  lhs.b = old_lhs.b * rhs.a - old_lhs.a * rhs.b;
  return lhs / rhs.norm();
}
template <typename T>
inline GenericComplex<T> operator/(const GenericComplex<T>& lhs,
                                   const GenericComplex<T>& rhs) {
  return GenericComplex<T>(lhs.a * rhs.a + lhs.b * rhs.b,
                           lhs.b * rhs.a - lhs.a * rhs.b) /
         rhs.norm();
}
template <typename T, typename U>
inline GenericComplex<T>& operator*=(GenericComplex<T>& lhs, const U val) {
  lhs.a *= val;
  lhs.b *= val;
  return lhs;
}
template <typename T, typename U>
inline GenericComplex<T>& operator*(GenericComplex<T> lhs, const U val) {
  return lhs *= val;
}
template <typename T, typename U>
inline GenericComplex<T>& operator/=(GenericComplex<T>& lhs, const U val) {
  lhs.a /= val;
  lhs.b /= val;
  return lhs;
}
template <typename T, typename U>
inline GenericComplex<T>& operator/(GenericComplex<T> lhs, const U val) {
  return lhs /= val;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const GenericComplex<T>& v) {
  std::cout << "(" << v.a << ", " << v.b << ")";
  return os;
}
const size_t maximum_step_size = 4096;
template <typename Complex>
void faster_fourier_transform(const size_t n,
                              const vector<vector<Complex>>& roots,
                              Complex* result, Complex* buffer,
                              const Complex* v, const size_t step) {
  if (n == 1) {
    result[0] = v[0];
    return;
  }
  assert(n % 2 == 0);
  const size_t h = n / 2;
  if (step >= maximum_step_size) {
    const size_t two_step = step + step;
    for (size_t i = 0, pos = 0; i < h; i += 1, pos += two_step)
      buffer[i] = v[pos];
    faster_fourier_transform(h, roots, result, buffer + h, buffer, 1);
    for (size_t i = 0, pos = step; i < h; i += 1, pos += two_step)
      buffer[i] = v[pos];
    faster_fourier_transform(h, roots, result + h, buffer + h, buffer, 1);
  } else {
    const size_t h = n / 2;
    faster_fourier_transform(h, roots, result, buffer, v, step * 2);
    faster_fourier_transform(h, roots, result + h, buffer, v + step, step * 2);
  }
  size_t root_pot = 0;
  while (((size_t)1 << root_pot) < n) ++root_pot;
  for (size_t i = 0; i < h; ++i) {
    const Complex even = result[i];
    const Complex odd = result[h + i] * roots[root_pot][i];
    result[i] += odd;
    result[h + i] = even - odd;
  }
}
template <typename Complex>
inline void faster_fourier_transform(const size_t n,
                                     const vector<vector<Complex>>& roots,
                                     vector<Complex>& result,
                                     const vector<Complex>& v) {
  static vector<Complex> buffer;
  const size_t required_buffer_size = v.size() / maximum_step_size;
  if (buffer.size() < required_buffer_size) buffer.resize(required_buffer_size);
  faster_fourier_transform(n, roots, &result[0], &buffer[0], &v[0], 1);
}
template <typename Complex, typename T>
const vector<Complex>& convolution_helper_complex(const vector<T>& _lhs,
                                                  const vector<T>& _rhs,
                                                  size_t& n) {
  static vector<Complex> aux1, aux2, aux3;
  const size_t lhs_size = _lhs.size();
  const size_t rhs_size = _rhs.size();
  assert(lhs_size != 0 && rhs_size != 0);
  n = 1;
  while (n < lhs_size) n *= 2;
  while (n < rhs_size) n *= 2;
  n *= 2;
  aux1.resize(lhs_size);
  aux2.resize(rhs_size);
  copy(_lhs.begin(), _lhs.end(), aux1.begin());
  copy(_rhs.begin(), _rhs.end(), aux2.begin());
  aux1.resize(n);
  aux2.resize(n);
  aux3.resize(n);
  Complex::ensure_roots(n);
  faster_fourier_transform(n, Complex::roots, aux3, aux1);
  faster_fourier_transform(n, Complex::roots, aux1, aux2);
  for (size_t i = 0; i < n; ++i) aux1[i] *= aux3[i];
  faster_fourier_transform(n, Complex::roots_inv, aux3, aux1);
  return aux3;
}
template <typename Complex, typename T>
const vector<Complex>& convolution_helper_real(const vector<T>& _lhs,
                                               const vector<T>& _rhs,
                                               size_t& n) {
  static vector<Complex> aux1, aux2;
  const size_t lhs_size = _lhs.size();
  const size_t rhs_size = _rhs.size();
  assert(lhs_size != 0 && rhs_size != 0);
  n = 1;
  while (n < lhs_size) n *= 2;
  while (n < rhs_size) n *= 2;
  n *= 2;
  aux1.resize(0);
  aux1.resize(n);
  for (size_t i = 0; i < lhs_size; ++i) aux1[i].a = _lhs[i];
  for (size_t i = 0; i < rhs_size; ++i) aux1[i].b = _rhs[i];
  aux2.resize(n);
  Complex::ensure_roots(n);
  faster_fourier_transform(n, Complex::roots, aux2, aux1);
  for (size_t i = 0; i < n; ++i) aux2[i] *= aux2[i] / n;
  faster_fourier_transform(n, Complex::roots_inv, aux1, aux2);
  return aux1;
}
template <typename Complex>
vector<Complex> convolution_complex(const vector<Complex>& lhs,
                                    const vector<Complex>& rhs) {
  const size_t ans_size = lhs.size() + rhs.size() - 1;
  size_t n;
  const vector<Complex>& ans_v =
      convolution_helper_complex<Complex>(lhs, rhs, n);
  vector<Complex> ans(ans_size);
  for (size_t i = 0; i < ans_size; ++i) ans[i] = ans_v[i] / n;
  return ans;
}
template <typename Real>
vector<Real> convolution_real(const vector<Real>& lhs,
                              const vector<Real>& rhs) {
  using Complex = GenericComplex<double>;
  const size_t ans_size = lhs.size() + rhs.size() - 1;
  size_t n;
  const vector<Complex>& ans_v = convolution_helper_real<Complex>(lhs, rhs, n);
  vector<Real> ans(ans_size);
  for (size_t i = 0; i < ans_size; ++i) ans[i] = ans_v[i].b / 2;
  return ans;
}
vector<long long> convolution_integer(const vector<long long>& lhs,
                                      const vector<long long>& rhs) {
  using Complex = GenericComplex<double>;
  const size_t ans_size = lhs.size() + rhs.size() - 1;
  size_t n;
  const vector<Complex>& ans_v = convolution_helper_real<Complex>(lhs, rhs, n);
  vector<long long> ans(ans_size);
  for (size_t i = 0; i < ans_size; ++i) ans[i] = round(ans_v[i].b / 2);
  return ans;
}
vector<long long> shift_convolution_integer(const vector<long long>& lhs,
                                            vector<long long>& rhs) {
  if (rhs.empty()) return {};
  reverse(rhs.begin(), rhs.end());
  const size_t m = rhs.size();
  const auto& ret = convolution_integer(lhs, rhs);
  reverse(rhs.begin(), rhs.end());
  return vector<long long>(ret.begin() + m - 1, ret.end());
}
vector<long long> convolution_integer_modsplit(const vector<long long>& lhs,
                                               const vector<long long>& rhs,
                                               const long long mod = 1e12 +
                                                                     39) {
  using Complex = GenericComplex<double>;
  auto modmul = [mod](long long a, long long b) {
    return ((__int128)a * b) % mod;
  };
  static vector<Complex> aux1, aux2, aux3, aux4;
  const size_t lhs_size = lhs.size();
  const size_t rhs_size = rhs.size();
  const long long base = sqrtl(mod) + 0.5;
  const long long base2 = (base * base) % mod;
  assert(lhs_size != 0 && rhs_size != 0);
  size_t n = 1;
  while (n < lhs_size) n *= 2;
  while (n < rhs_size) n *= 2;
  n *= 2;
  Complex::ensure_roots(n);
  aux2.resize(0);
  aux2.resize(n);
  for (size_t i = 0; i < lhs_size; ++i)
    aux2[i] = {double(lhs[i] / base), double(lhs[i] % base)};
  aux1.resize(n);
  faster_fourier_transform(n, Complex::roots, aux1, aux2);
  aux3.resize(0);
  aux3.resize(n);
  for (size_t i = 0; i < rhs_size; ++i)
    aux3[i] = {double(rhs[i] / base), double(rhs[i] % base)};
  faster_fourier_transform(n, Complex::roots, aux2, aux3);
  aux4.resize(n);
  for (size_t i = 0; i < n; ++i) {
    size_t j = i ? n - i : 0;
    Complex a1 = (aux1[i] + aux1[j].conj()) * Complex(0.5, 0.0);
    Complex a2 = (aux1[i] - aux1[j].conj()) * Complex(0.0, -0.5);
    Complex b1 = (aux2[i] + aux2[j].conj()) * Complex(0.5, 0.0);
    Complex b2 = (aux2[i] - aux2[j].conj()) * Complex(0.0, -0.5);
    Complex c11 = a1 * b1, c12 = a1 * b2;
    Complex c21 = a2 * b1, c22 = a2 * b2;
    aux3[j] = c11 + c12 * Complex(0.0, 1.0);
    aux4[j] = c21 + c22 * Complex(0.0, 1.0);
  }
  faster_fourier_transform(n, Complex::roots_inv, aux1, aux3);
  faster_fourier_transform(n, Complex::roots_inv, aux2, aux4);
  const size_t ans_size = lhs.size() + rhs.size() - 1;
  vector<long long> ans(ans_size);
  for (size_t i = 0; i < ans_size; i++) {
    size_t j = i ? n - i : 0;
    long long x = round(aux1[j].a / n);
    long long y1 = round(aux1[j].b / n);
    long long y2 = round(aux2[j].a / n);
    long long z = round(aux2[j].b / n);
    ans[i] = 0;
    ans[i] += modmul(x % mod, base2);
    ans[i] += modmul((y1 + y2) % mod, base);
    ans[i] += z;
    ans[i] %= mod;
  }
  return ans;
}
const int LOG = 17;
const int MOD = 998244353;
int N, K;
int32_t main() {
  scanf("%d %d", &N, &K);
  vector<long long> achievable(10, 0);
  for (int i = 0; i < K; i++) {
    int d;
    scanf("%d", &d);
    achievable[d] = 1;
  }
  int goal = N / 2;
  vector<long long> result(1, 0);
  result[0] = 1;
  while (goal > 0) {
    if (goal & 1)
      result = convolution_integer_modsplit(result, achievable, MOD);
    goal >>= 1;
    if (goal > 0)
      achievable = convolution_integer_modsplit(achievable, achievable, MOD);
  }
  long long answer = 0;
  for (long long x : result) assert(x >= 0 && x < MOD);
  for (long long x : result) answer = (answer + (long long)x * x) % MOD;
  printf("%lld\n", answer);
}