#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt,abm,mmx,sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;
using cpx = complex<double>;
const double PI = acos(-1);
const int MOD = 998244353;
int reverse(unsigned i) {
  i = (i & 0x55555555) << 1 | ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) << 2 | ((i >> 2) & 0x33333333);
  i = (i & 0x0f0f0f0f) << 4 | ((i >> 4) & 0x0f0f0f0f);
  i = (i << 24) | ((i & 0xff00) << 8) | ((i >> 8) & 0xff00) | (i >> 24);
  return i;
}
void fft(vector<cpx> &x, bool inverse) {
  int n = x.size();
  int shift = 32 - __builtin_ctz(n);
  for (int i = 1; i < n; i++) {
    int j = reverse((unsigned)i << shift);
    if (i < j) {
      swap(x[i], x[j]);
    }
  }
  for (int len = 2; len <= n; len <<= 1) {
    int halfLen = len >> 1;
    vector<cpx> w(halfLen);
    for (int i = 0; i < halfLen; i++) {
      double angle = 2 * PI * i / len * (inverse ? -1 : 1);
      w[i] = cpx(cos(angle), sin(angle));
    }
    for (int i = 0; i < n; i += len) {
      for (int j = 0; j < halfLen; j++) {
        cpx u = x[i + j];
        cpx v = x[i + j + halfLen] * w[j];
        x[i + j] = u + v;
        x[i + j + halfLen] = u - v;
      }
    }
  }
  if (inverse) {
    for (int i = 0; i < n; i++) {
      x[i] /= n;
    }
  }
}
vector<int> multiply_mod(const vector<int> &a, const vector<int> &b, int mod) {
  int need = a.size() + b.size() - 1;
  int n = max(2, 1 << (32 - (need == 1 ? 0 : __builtin_clz(need - 1))));
  vector<cpx> A(n);
  for (int i = 0; i < a.size(); i++) {
    int x = (a[i] % mod + mod) % mod;
    A[i] = cpx(x & ((1 << 15) - 1), x >> 15);
  }
  fft(A, false);
  vector<cpx> B(n);
  for (int i = 0; i < b.size(); i++) {
    int x = (b[i] % mod + mod) % mod;
    B[i] = cpx(x & ((1 << 15) - 1), x >> 15);
  }
  fft(B, false);
  vector<cpx> fa(n);
  vector<cpx> fb(n);
  cpx r2(0, -1), r3(0.25, 0), r4(0, -0.25), r5(0, 1);
  for (int i = 0; i < n; i++) {
    int j = (n - i) & (n - 1);
    cpx a1 = (A[i] + conj(A[j]));
    cpx a2 = (A[i] - conj(A[j])) * r2;
    cpx b1 = (B[i] + conj(B[j])) * r3;
    cpx b2 = (B[i] - conj(B[j])) * r4;
    fa[i] = a1 * b1 + a2 * b2 * r5;
    fb[i] = a1 * b2 + a2 * b1;
  }
  fft(fa, true);
  fft(fb, true);
  vector<int> res(need);
  for (int i = 0; i < need; i++) {
    long long aa = (long long)(fa[i].real() + 0.5);
    long long bb = (long long)(fb[i].real() + 0.5);
    long long cc = (long long)(fa[i].imag() + 0.5);
    res[i] = (int)((aa + ((bb % mod) << 15) + ((cc % mod) << 30)) % mod);
  }
  return res;
}
void solve(istream &in, ostream &out) {
  int n, k;
  in >> n >> k;
  vector<int> v(10);
  for (int i = 0; i < k; ++i) {
    int d;
    in >> d;
    v[d] = 1;
  }
  vector<int> ans{1};
  int p = n / 2;
  while (true) {
    if (p & 1) ans = multiply_mod(ans, v, MOD);
    p >>= 1;
    if (!p) {
      break;
    }
    v = multiply_mod(v, v, MOD);
  }
  int res = 0;
  for (long long a : ans) res = (res + a * a) % MOD;
  out << res << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solve(in, out);
}

### Prompt

Your challenge is to write a CPP solution to 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>
#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt,abm,mmx,sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;
using cpx = complex<double>;
const double PI = acos(-1);
const int MOD = 998244353;
int reverse(unsigned i) {
  i = (i & 0x55555555) << 1 | ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) << 2 | ((i >> 2) & 0x33333333);
  i = (i & 0x0f0f0f0f) << 4 | ((i >> 4) & 0x0f0f0f0f);
  i = (i << 24) | ((i & 0xff00) << 8) | ((i >> 8) & 0xff00) | (i >> 24);
  return i;
}
void fft(vector<cpx> &x, bool inverse) {
  int n = x.size();
  int shift = 32 - __builtin_ctz(n);
  for (int i = 1; i < n; i++) {
    int j = reverse((unsigned)i << shift);
    if (i < j) {
      swap(x[i], x[j]);
    }
  }
  for (int len = 2; len <= n; len <<= 1) {
    int halfLen = len >> 1;
    vector<cpx> w(halfLen);
    for (int i = 0; i < halfLen; i++) {
      double angle = 2 * PI * i / len * (inverse ? -1 : 1);
      w[i] = cpx(cos(angle), sin(angle));
    }
    for (int i = 0; i < n; i += len) {
      for (int j = 0; j < halfLen; j++) {
        cpx u = x[i + j];
        cpx v = x[i + j + halfLen] * w[j];
        x[i + j] = u + v;
        x[i + j + halfLen] = u - v;
      }
    }
  }
  if (inverse) {
    for (int i = 0; i < n; i++) {
      x[i] /= n;
    }
  }
}
vector<int> multiply_mod(const vector<int> &a, const vector<int> &b, int mod) {
  int need = a.size() + b.size() - 1;
  int n = max(2, 1 << (32 - (need == 1 ? 0 : __builtin_clz(need - 1))));
  vector<cpx> A(n);
  for (int i = 0; i < a.size(); i++) {
    int x = (a[i] % mod + mod) % mod;
    A[i] = cpx(x & ((1 << 15) - 1), x >> 15);
  }
  fft(A, false);
  vector<cpx> B(n);
  for (int i = 0; i < b.size(); i++) {
    int x = (b[i] % mod + mod) % mod;
    B[i] = cpx(x & ((1 << 15) - 1), x >> 15);
  }
  fft(B, false);
  vector<cpx> fa(n);
  vector<cpx> fb(n);
  cpx r2(0, -1), r3(0.25, 0), r4(0, -0.25), r5(0, 1);
  for (int i = 0; i < n; i++) {
    int j = (n - i) & (n - 1);
    cpx a1 = (A[i] + conj(A[j]));
    cpx a2 = (A[i] - conj(A[j])) * r2;
    cpx b1 = (B[i] + conj(B[j])) * r3;
    cpx b2 = (B[i] - conj(B[j])) * r4;
    fa[i] = a1 * b1 + a2 * b2 * r5;
    fb[i] = a1 * b2 + a2 * b1;
  }
  fft(fa, true);
  fft(fb, true);
  vector<int> res(need);
  for (int i = 0; i < need; i++) {
    long long aa = (long long)(fa[i].real() + 0.5);
    long long bb = (long long)(fb[i].real() + 0.5);
    long long cc = (long long)(fa[i].imag() + 0.5);
    res[i] = (int)((aa + ((bb % mod) << 15) + ((cc % mod) << 30)) % mod);
  }
  return res;
}
void solve(istream &in, ostream &out) {
  int n, k;
  in >> n >> k;
  vector<int> v(10);
  for (int i = 0; i < k; ++i) {
    int d;
    in >> d;
    v[d] = 1;
  }
  vector<int> ans{1};
  int p = n / 2;
  while (true) {
    if (p & 1) ans = multiply_mod(ans, v, MOD);
    p >>= 1;
    if (!p) {
      break;
    }
    v = multiply_mod(v, v, MOD);
  }
  int res = 0;
  for (long long a : ans) res = (res + a * a) % MOD;
  out << res << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solve(in, out);
}

```