#include <bits/stdc++.h>
const int md = 998244353, inf = 1e9 + 7;
const long long hs = 199;
const long double eps = 1e-9, pi = acosl(-1);
const long double PI = pi;
using namespace std;
const int maxn = (1 << 20) + 5;
struct Complex {
  double real, imag;
  Complex conj() { return Complex(real, -imag); }
  Complex(double a = 0, double b = 0) : real(a), imag(b) {}
  Complex operator+(const Complex &o) const {
    return Complex(real + o.real, imag + o.imag);
  }
  Complex operator-(const Complex &o) const {
    return Complex(real - o.real, imag - o.imag);
  }
  Complex operator*(const Complex &o) const {
    return Complex(real * o.real - imag * o.imag,
                   real * o.imag + imag * o.real);
  }
  Complex operator/(double o) const { return Complex(real / o, imag / o); }
  void operator*=(Complex o) { *this = *this * o; }
  void operator/=(double o) { real /= o, imag /= o; }
};
const int ms = 1 << 22;
int bits[ms];
Complex root[ms];
void initFFT() {
  root[1] = Complex(1);
  for (int len = 2; len < ms; len += len) {
    Complex z(cos(PI / len), sin(PI / len));
    for (int i = len / 2; i < len; i++) {
      root[2 * i] = root[i];
      root[2 * i + 1] = root[i] * z;
    }
  }
}
void pre(int n) {
  int LOG = 0;
  while (1 << (LOG + 1) < n) {
    LOG++;
  }
  for (int i = 1; i < n; i++) {
    bits[i] = (bits[i >> 1] >> 1) | ((i & 1) << LOG);
  }
}
std::vector<Complex> fft(std::vector<Complex> a, bool inv = false) {
  int n = a.size();
  pre(n);
  if (inv) {
    std::reverse(a.begin() + 1, a.end());
  }
  for (int i = 0; i < n; i++) {
    int to = bits[i];
    if (to > i) {
      std::swap(a[to], a[i]);
    }
  }
  for (int len = 1; len < n; len *= 2) {
    for (int i = 0; i < n; i += 2 * len) {
      for (int j = 0; j < len; j++) {
        Complex u = a[i + j], v = a[i + j + len] * root[len + j];
        a[i + j] = u + v;
        a[i + j + len] = u - v;
      }
    }
  }
  if (inv) {
    for (int i = 0; i < n; i++) a[i] /= n;
  }
  return a;
}
void fft2in1(std::vector<Complex> &a, std::vector<Complex> &b) {
  int n = (int)a.size();
  for (int i = 0; i < n; i++) {
    a[i] = Complex(a[i].real, b[i].real);
  }
  auto c = fft(a);
  for (int i = 0; i < n; i++) {
    a[i] = (c[i] + c[(n - i) % n].conj()) * Complex(0.5, 0);
    b[i] = (c[i] - c[(n - i) % n].conj()) * Complex(0, -0.5);
  }
}
void ifft2in1(std::vector<Complex> &a, std::vector<Complex> &b) {
  int n = (int)a.size();
  for (int i = 0; i < n; i++) {
    a[i] = a[i] + b[i] * Complex(0, 1);
  }
  a = fft(a, true);
  for (int i = 0; i < n; i++) {
    b[i] = Complex(a[i].imag, 0);
    a[i] = Complex(a[i].real, 0);
  }
}
std::vector<Complex> C[4];
std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b,
                     long long cut = 1 << 16) {
  int n = (int)a.size();
  for (int i = 0; i < 4; i++) {
    C[i].resize(n);
  }
  for (int i = 0; i < n; i++) {
    C[0][i] = a[i] % cut;
    C[1][i] = a[i] / cut;
    C[2][i] = b[i] % cut;
    C[3][i] = b[i] / cut;
  }
  fft2in1(C[0], C[1]);
  fft2in1(C[2], C[3]);
  for (int i = 0; i < n; i++) {
    Complex cur[4];
    for (int j = 0; j < 4; j++) cur[j] = C[j / 2 + 2][i] * C[j % 2][i];
    for (int j = 0; j < 4; j++) C[j][i] = cur[j];
  }
  ifft2in1(C[0], C[1]);
  ifft2in1(C[2], C[3]);
  std::vector<int> ans(n, 0);
  for (int i = 0; i < n; i++) {
    ans[i] += (long long)(C[0][i].real + 0.5) % md;
    ans[i] %= md;
    ans[i] += (long long)(C[1][i].real + C[2][i].real + 0.5) * cut % md;
    ans[i] %= md;
    ans[i] += (long long)(C[3][i].real + 0.5) * cut % md * cut % md;
    ans[i] %= md;
  }
  return ans;
}
vector<int> p1, p2;
void mult(vector<int> &a, const vector<int> &b) {
  int n = a.size() + b.size();
  while (n != (n & -n)) n += (n & -n);
  p1.resize(0);
  p2.resize(0);
  for (auto &i : a) p1.push_back(i);
  for (auto &i : b) p2.push_back(i);
  while (p1.size() < n) p1.push_back(0);
  while (p2.size() < n) p2.push_back(0);
  a = mul(p1, p2, (long long)(1 << 15));
  while (a.size() && a.back() == 0) a.pop_back();
}
vector<int> pw(vector<int> a, int e) {
  vector<int> rtn = {1};
  while (e) {
    if (e & 1) mult(rtn, a);
    e /= 2;
    if (e) mult(a, a);
  }
  return rtn;
}
int n, k;
vector<int> a(10, 0);
int main() {
  initFFT();
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  int x;
  for (int i = 0; i < k; i++) {
    cin >> x;
    a[x] = 1;
  }
  vector<int> A = pw(a, n / 2);
  int ans = 0;
  for (auto &i : A) {
    ans = (ans + (long long)i * i) % md;
  }
  return cout << ans << '\n', 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
const int md = 998244353, inf = 1e9 + 7;
const long long hs = 199;
const long double eps = 1e-9, pi = acosl(-1);
const long double PI = pi;
using namespace std;
const int maxn = (1 << 20) + 5;
struct Complex {
  double real, imag;
  Complex conj() { return Complex(real, -imag); }
  Complex(double a = 0, double b = 0) : real(a), imag(b) {}
  Complex operator+(const Complex &o) const {
    return Complex(real + o.real, imag + o.imag);
  }
  Complex operator-(const Complex &o) const {
    return Complex(real - o.real, imag - o.imag);
  }
  Complex operator*(const Complex &o) const {
    return Complex(real * o.real - imag * o.imag,
                   real * o.imag + imag * o.real);
  }
  Complex operator/(double o) const { return Complex(real / o, imag / o); }
  void operator*=(Complex o) { *this = *this * o; }
  void operator/=(double o) { real /= o, imag /= o; }
};
const int ms = 1 << 22;
int bits[ms];
Complex root[ms];
void initFFT() {
  root[1] = Complex(1);
  for (int len = 2; len < ms; len += len) {
    Complex z(cos(PI / len), sin(PI / len));
    for (int i = len / 2; i < len; i++) {
      root[2 * i] = root[i];
      root[2 * i + 1] = root[i] * z;
    }
  }
}
void pre(int n) {
  int LOG = 0;
  while (1 << (LOG + 1) < n) {
    LOG++;
  }
  for (int i = 1; i < n; i++) {
    bits[i] = (bits[i >> 1] >> 1) | ((i & 1) << LOG);
  }
}
std::vector<Complex> fft(std::vector<Complex> a, bool inv = false) {
  int n = a.size();
  pre(n);
  if (inv) {
    std::reverse(a.begin() + 1, a.end());
  }
  for (int i = 0; i < n; i++) {
    int to = bits[i];
    if (to > i) {
      std::swap(a[to], a[i]);
    }
  }
  for (int len = 1; len < n; len *= 2) {
    for (int i = 0; i < n; i += 2 * len) {
      for (int j = 0; j < len; j++) {
        Complex u = a[i + j], v = a[i + j + len] * root[len + j];
        a[i + j] = u + v;
        a[i + j + len] = u - v;
      }
    }
  }
  if (inv) {
    for (int i = 0; i < n; i++) a[i] /= n;
  }
  return a;
}
void fft2in1(std::vector<Complex> &a, std::vector<Complex> &b) {
  int n = (int)a.size();
  for (int i = 0; i < n; i++) {
    a[i] = Complex(a[i].real, b[i].real);
  }
  auto c = fft(a);
  for (int i = 0; i < n; i++) {
    a[i] = (c[i] + c[(n - i) % n].conj()) * Complex(0.5, 0);
    b[i] = (c[i] - c[(n - i) % n].conj()) * Complex(0, -0.5);
  }
}
void ifft2in1(std::vector<Complex> &a, std::vector<Complex> &b) {
  int n = (int)a.size();
  for (int i = 0; i < n; i++) {
    a[i] = a[i] + b[i] * Complex(0, 1);
  }
  a = fft(a, true);
  for (int i = 0; i < n; i++) {
    b[i] = Complex(a[i].imag, 0);
    a[i] = Complex(a[i].real, 0);
  }
}
std::vector<Complex> C[4];
std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b,
                     long long cut = 1 << 16) {
  int n = (int)a.size();
  for (int i = 0; i < 4; i++) {
    C[i].resize(n);
  }
  for (int i = 0; i < n; i++) {
    C[0][i] = a[i] % cut;
    C[1][i] = a[i] / cut;
    C[2][i] = b[i] % cut;
    C[3][i] = b[i] / cut;
  }
  fft2in1(C[0], C[1]);
  fft2in1(C[2], C[3]);
  for (int i = 0; i < n; i++) {
    Complex cur[4];
    for (int j = 0; j < 4; j++) cur[j] = C[j / 2 + 2][i] * C[j % 2][i];
    for (int j = 0; j < 4; j++) C[j][i] = cur[j];
  }
  ifft2in1(C[0], C[1]);
  ifft2in1(C[2], C[3]);
  std::vector<int> ans(n, 0);
  for (int i = 0; i < n; i++) {
    ans[i] += (long long)(C[0][i].real + 0.5) % md;
    ans[i] %= md;
    ans[i] += (long long)(C[1][i].real + C[2][i].real + 0.5) * cut % md;
    ans[i] %= md;
    ans[i] += (long long)(C[3][i].real + 0.5) * cut % md * cut % md;
    ans[i] %= md;
  }
  return ans;
}
vector<int> p1, p2;
void mult(vector<int> &a, const vector<int> &b) {
  int n = a.size() + b.size();
  while (n != (n & -n)) n += (n & -n);
  p1.resize(0);
  p2.resize(0);
  for (auto &i : a) p1.push_back(i);
  for (auto &i : b) p2.push_back(i);
  while (p1.size() < n) p1.push_back(0);
  while (p2.size() < n) p2.push_back(0);
  a = mul(p1, p2, (long long)(1 << 15));
  while (a.size() && a.back() == 0) a.pop_back();
}
vector<int> pw(vector<int> a, int e) {
  vector<int> rtn = {1};
  while (e) {
    if (e & 1) mult(rtn, a);
    e /= 2;
    if (e) mult(a, a);
  }
  return rtn;
}
int n, k;
vector<int> a(10, 0);
int main() {
  initFFT();
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  int x;
  for (int i = 0; i < k; i++) {
    cin >> x;
    a[x] = 1;
  }
  vector<int> A = pw(a, n / 2);
  int ans = 0;
  for (auto &i : A) {
    ans = (ans + (long long)i * i) % md;
  }
  return cout << ans << '\n', 0;
}

```