#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const long long MO = 998244353;
const long long G = 3;
const long long Inv2 = (MO + 1) / 2;
const bool debug = true;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c;
  T t = 1;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  if (c == '-') {
    t = -1;
    c = getchar();
  }
  do (x *= 10) += (c - '0');
  while ((c = getchar()) >= '0' && c <= '9');
  x *= t;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x), read(args...);
}
template <typename T>
inline void write(T x) {
  int len = 0;
  char c[21];
  if (x < 0) putchar('-'), x *= (-1);
  do {
    ++len;
    c[len] = (x % 10) + '0';
  } while (x /= 10);
  for (int i = (len); i >= (1); --i) putchar(c[i]);
}
int d[15], len, rev[1048580];
long long a[1048580], b[1048580];
inline long long fpow(long long n, long long k) {
  long long t = 1;
  while (k) {
    if (k & 1) t = (t * n) % MO;
    n = (n * n) % MO;
    k >>= 1;
  }
  return t;
}
inline void ntt(long long *arr, int f, int n) {
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(arr[i], arr[rev[i]]);
  for (int i = 1; i < n; i <<= 1) {
    long long gn = fpow(G, (MO - 1) / (i << 1));
    if (f == -1) gn = fpow(gn, MO - 2);
    for (int j = 0; j < n; j += i << 1) {
      long long w = 1;
      for (int k = 0; k < i; k++) {
        long long x = arr[j + k], y = w * arr[j + k + i] % MO;
        arr[j + k] = (x + y) % MO;
        arr[j + k + i] = (x - y + MO) % MO;
        w = (w * gn) % MO;
      }
    }
  }
}
int k;
int solve(const int &L, const int &R) {
  if (L == R) {
    for (int i = (0); i <= (9); ++i) a[i] = 0;
    for (int i = (1); i <= (k); ++i) a[d[i]] = 1;
    return 9;
  }
  int mid = (L + R) >> 1, m, n;
  n = solve(L, mid);
  if (R - mid - 1 == mid - L) {
    m = n;
    for (int i = (0); i <= (m); ++i) b[i] = a[i];
  } else {
    queue<long long> q;
    for (int i = (0); i <= (n); ++i) q.push(a[i]), a[i] = 0;
    m = solve(mid + 1, R);
    for (int i = (0); i <= (m); ++i) b[i] = a[i];
    for (int i = (0); i <= (n); ++i) a[i] = q.front(), q.pop();
  }
  int n1 = n + 1, m1 = m + 1;
  m += n, len = rev[0] = 0;
  for (n = 1; n <= m; n <<= 1) len++;
  for (int i = (n1); i <= (n); ++i) a[i] = 0;
  for (int i = (m1); i <= (n); ++i) b[i] = 0;
  for (int i = 0; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((long long)(i & 1) << (len - 1));
  ntt(a, 1, n), ntt(b, 1, n);
  for (int i = 0; i <= n; i++) a[i] = (a[i] * b[i]) % MO;
  ntt(a, -1, n);
  int invn = fpow(n, MO - 2);
  for (int i = 0; i <= m; i++) a[i] = a[i] * invn % MO;
  return m;
}
inline int ac() {
  int n;
  read(n, k);
  for (int i = (1); i <= (k); ++i) read(d[i]);
  n = solve(1, n >> 1);
  long long ans = 0;
  for (int i = (0); i <= (n); ++i) (ans += (a[i] * a[i] % MO)) %= MO;
  write(ans);
  return 0;
}
int main() {
  ac();
  return 0;
}

### Prompt

Please formulate 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>
using namespace std;
const double PI = acos(-1);
const long long MO = 998244353;
const long long G = 3;
const long long Inv2 = (MO + 1) / 2;
const bool debug = true;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c;
  T t = 1;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  if (c == '-') {
    t = -1;
    c = getchar();
  }
  do (x *= 10) += (c - '0');
  while ((c = getchar()) >= '0' && c <= '9');
  x *= t;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x), read(args...);
}
template <typename T>
inline void write(T x) {
  int len = 0;
  char c[21];
  if (x < 0) putchar('-'), x *= (-1);
  do {
    ++len;
    c[len] = (x % 10) + '0';
  } while (x /= 10);
  for (int i = (len); i >= (1); --i) putchar(c[i]);
}
int d[15], len, rev[1048580];
long long a[1048580], b[1048580];
inline long long fpow(long long n, long long k) {
  long long t = 1;
  while (k) {
    if (k & 1) t = (t * n) % MO;
    n = (n * n) % MO;
    k >>= 1;
  }
  return t;
}
inline void ntt(long long *arr, int f, int n) {
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(arr[i], arr[rev[i]]);
  for (int i = 1; i < n; i <<= 1) {
    long long gn = fpow(G, (MO - 1) / (i << 1));
    if (f == -1) gn = fpow(gn, MO - 2);
    for (int j = 0; j < n; j += i << 1) {
      long long w = 1;
      for (int k = 0; k < i; k++) {
        long long x = arr[j + k], y = w * arr[j + k + i] % MO;
        arr[j + k] = (x + y) % MO;
        arr[j + k + i] = (x - y + MO) % MO;
        w = (w * gn) % MO;
      }
    }
  }
}
int k;
int solve(const int &L, const int &R) {
  if (L == R) {
    for (int i = (0); i <= (9); ++i) a[i] = 0;
    for (int i = (1); i <= (k); ++i) a[d[i]] = 1;
    return 9;
  }
  int mid = (L + R) >> 1, m, n;
  n = solve(L, mid);
  if (R - mid - 1 == mid - L) {
    m = n;
    for (int i = (0); i <= (m); ++i) b[i] = a[i];
  } else {
    queue<long long> q;
    for (int i = (0); i <= (n); ++i) q.push(a[i]), a[i] = 0;
    m = solve(mid + 1, R);
    for (int i = (0); i <= (m); ++i) b[i] = a[i];
    for (int i = (0); i <= (n); ++i) a[i] = q.front(), q.pop();
  }
  int n1 = n + 1, m1 = m + 1;
  m += n, len = rev[0] = 0;
  for (n = 1; n <= m; n <<= 1) len++;
  for (int i = (n1); i <= (n); ++i) a[i] = 0;
  for (int i = (m1); i <= (n); ++i) b[i] = 0;
  for (int i = 0; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((long long)(i & 1) << (len - 1));
  ntt(a, 1, n), ntt(b, 1, n);
  for (int i = 0; i <= n; i++) a[i] = (a[i] * b[i]) % MO;
  ntt(a, -1, n);
  int invn = fpow(n, MO - 2);
  for (int i = 0; i <= m; i++) a[i] = a[i] * invn % MO;
  return m;
}
inline int ac() {
  int n;
  read(n, k);
  for (int i = (1); i <= (k); ++i) read(d[i]);
  n = solve(1, n >> 1);
  long long ans = 0;
  for (int i = (0); i <= (n); ++i) (ans += (a[i] * a[i] % MO)) %= MO;
  write(ans);
  return 0;
}
int main() {
  ac();
  return 0;
}

```