#include <bits/stdc++.h>
using namespace std;
int r[(1 << 21) + 5], inv[(1 << 21) + 5] = {1, 1}, w[(1 << 21) + 5] = {1},
                                      lg[(1 << 21) + 5], wlen;
int Pow(int base, int k) {
  int ret = 1;
  for (; k; k >>= 1, base = 1ll * base * base % 998244353)
    if (k & 1) ret = 1ll * ret * base % 998244353;
  return ret;
}
void Init(int n) {
  for (wlen = 1; n >= (wlen << 1); wlen <<= 1)
    ;
  for (int i = 1, pw = Pow(3, (998244353 - 1) / (2 * wlen)); i <= 2 * wlen; i++)
    w[i] = 1ll * w[i - 1] * pw % 998244353;
  for (int i = 2; i <= 2 * wlen; i++)
    lg[i] = lg[i >> 1] + 1,
    inv[i] = 1ll * (998244353 - 998244353 / i) * inv[998244353 % i] % 998244353;
}
inline void NTT(int A[(1 << 21) + 5], int n, int tp) {
  int lgn = lg[n];
  for (int i = 1; i < n; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lgn - 1));
  for (int i = 1; i < n; i++)
    if (i < r[i]) swap(A[i], A[r[i]]);
  for (int L = 2; L <= n; L <<= 1)
    for (int st = 0, l = L >> 1, inc = wlen / l; st < n; st += L)
      for (int k = st, x = 0, tmp; k < st + l; k++, x += inc)
        tmp = 1ll * (tp == 1 ? w[x] : w[2 * wlen - x]) * A[k + l] % 998244353,
        A[k + l] = (A[k] - tmp) % 998244353, A[k] = (A[k] + tmp) % 998244353;
  if (tp == -1)
    for (int i = 0, inv = Pow(n, 998244353 - 2); i < n; i++)
      A[i] = 1ll * A[i] * inv % 998244353;
}
void Inv(int *A, int *B, int n) {
  B[0] = Pow(A[0], 998244353 - 2), B[1] = 0;
  static int tmp[(1 << 21) + 5];
  for (int k = 2; k < (n << 1); k <<= 1) {
    for (int i = 0; i < (k << 1); i++)
      tmp[i] = i < k ? A[i] : 0, B[i] = i < k ? B[i] : 0;
    NTT(tmp, k << 1, 1), NTT(B, k << 1, 1);
    for (int i = 0; i < (k << 1); i++)
      B[i] = 1ll * B[i] * (2 - 1ll * B[i] * tmp[i] % 998244353) % 998244353;
    NTT(B, k << 1, -1);
    for (int i = min(n, k); i < (k << 1); i++) B[i] = 0;
  }
}
void cLn(int *A, int *B, int n) {
  Inv(A, B, n);
  static int tmp[(1 << 21) + 5];
  int lgn = lg[n - 1] + 2, len = 1 << lgn;
  for (int i = 0; i < len; i++)
    tmp[i] = i < n - 1 ? 1ll * A[i + 1] * (i + 1) % 998244353 : 0,
    B[i] = i < n ? B[i] : 0;
  NTT(tmp, len, 1), NTT(B, len, 1);
  for (int i = 0; i < len; i++) tmp[i] = 1ll * tmp[i] * B[i] % 998244353;
  NTT(tmp, len, -1);
  B[0] = 0;
  for (int i = 1; i < n; i++) B[i] = 1ll * tmp[i - 1] * inv[i] % 998244353;
  for (int i = n; i < len; i++) B[i] = 0;
}
void eXp(int *A, int *B, int n) {
  B[0] = 1, B[1] = 0;
  static int tmp[(1 << 21) + 5];
  for (int k = 2; k < (n << 1); k <<= 1) {
    cLn(B, tmp, k);
    for (int i = 0; i < (k << 1); i++)
      tmp[i] = i < k ? ((i == 0) - tmp[i] + A[i]) % 998244353 : 0,
      B[i] = i < k ? B[i] : 0;
    NTT(tmp, k << 1, 1), NTT(B, k << 1, 1);
    for (int i = 0; i < (k << 1); i++) B[i] = 1ll * B[i] * tmp[i] % 998244353;
    NTT(B, k << 1, -1);
    for (int i = min(n, k); i < (k << 1); i++) B[i] = 0;
  }
}
void Pow(int *A, int *B, int n, int k) {
  int lgn = lg[n - 1] + 2, len = 1 << lgn;
  for (int i = 0; i < len; i++) B[i] = i < n ? A[i] : 0;
  NTT(B, len, 1);
  for (int i = 0; i < len; i++) B[i] = Pow(B[i], k);
  NTT(B, len, -1);
}
int a[(1 << 21) + 5], b[(1 << 21) + 5];
int main() {
  int n, k, d[20] = {};
  scanf("%d%d", &n, &k);
  for (int i = 0; i < k; i++) scanf("%d", &d[i]);
  sort(d, d + k);
  for (int i = 0; i < k; i++) a[d[i] - d[0]]++;
  int tp = d[k - 1] - d[0];
  Init(n * 10);
  Pow(a, b, n / 2 * tp + 1, n / 2);
  int ans = 0;
  for (int i = 0; i < n * 5; i++)
    ans = (ans + 1ll * b[i] * b[i] % 998244353) % 998244353;
  printf("%d\n", (ans + 998244353) % 998244353);
}

### 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>
using namespace std;
int r[(1 << 21) + 5], inv[(1 << 21) + 5] = {1, 1}, w[(1 << 21) + 5] = {1},
                                      lg[(1 << 21) + 5], wlen;
int Pow(int base, int k) {
  int ret = 1;
  for (; k; k >>= 1, base = 1ll * base * base % 998244353)
    if (k & 1) ret = 1ll * ret * base % 998244353;
  return ret;
}
void Init(int n) {
  for (wlen = 1; n >= (wlen << 1); wlen <<= 1)
    ;
  for (int i = 1, pw = Pow(3, (998244353 - 1) / (2 * wlen)); i <= 2 * wlen; i++)
    w[i] = 1ll * w[i - 1] * pw % 998244353;
  for (int i = 2; i <= 2 * wlen; i++)
    lg[i] = lg[i >> 1] + 1,
    inv[i] = 1ll * (998244353 - 998244353 / i) * inv[998244353 % i] % 998244353;
}
inline void NTT(int A[(1 << 21) + 5], int n, int tp) {
  int lgn = lg[n];
  for (int i = 1; i < n; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lgn - 1));
  for (int i = 1; i < n; i++)
    if (i < r[i]) swap(A[i], A[r[i]]);
  for (int L = 2; L <= n; L <<= 1)
    for (int st = 0, l = L >> 1, inc = wlen / l; st < n; st += L)
      for (int k = st, x = 0, tmp; k < st + l; k++, x += inc)
        tmp = 1ll * (tp == 1 ? w[x] : w[2 * wlen - x]) * A[k + l] % 998244353,
        A[k + l] = (A[k] - tmp) % 998244353, A[k] = (A[k] + tmp) % 998244353;
  if (tp == -1)
    for (int i = 0, inv = Pow(n, 998244353 - 2); i < n; i++)
      A[i] = 1ll * A[i] * inv % 998244353;
}
void Inv(int *A, int *B, int n) {
  B[0] = Pow(A[0], 998244353 - 2), B[1] = 0;
  static int tmp[(1 << 21) + 5];
  for (int k = 2; k < (n << 1); k <<= 1) {
    for (int i = 0; i < (k << 1); i++)
      tmp[i] = i < k ? A[i] : 0, B[i] = i < k ? B[i] : 0;
    NTT(tmp, k << 1, 1), NTT(B, k << 1, 1);
    for (int i = 0; i < (k << 1); i++)
      B[i] = 1ll * B[i] * (2 - 1ll * B[i] * tmp[i] % 998244353) % 998244353;
    NTT(B, k << 1, -1);
    for (int i = min(n, k); i < (k << 1); i++) B[i] = 0;
  }
}
void cLn(int *A, int *B, int n) {
  Inv(A, B, n);
  static int tmp[(1 << 21) + 5];
  int lgn = lg[n - 1] + 2, len = 1 << lgn;
  for (int i = 0; i < len; i++)
    tmp[i] = i < n - 1 ? 1ll * A[i + 1] * (i + 1) % 998244353 : 0,
    B[i] = i < n ? B[i] : 0;
  NTT(tmp, len, 1), NTT(B, len, 1);
  for (int i = 0; i < len; i++) tmp[i] = 1ll * tmp[i] * B[i] % 998244353;
  NTT(tmp, len, -1);
  B[0] = 0;
  for (int i = 1; i < n; i++) B[i] = 1ll * tmp[i - 1] * inv[i] % 998244353;
  for (int i = n; i < len; i++) B[i] = 0;
}
void eXp(int *A, int *B, int n) {
  B[0] = 1, B[1] = 0;
  static int tmp[(1 << 21) + 5];
  for (int k = 2; k < (n << 1); k <<= 1) {
    cLn(B, tmp, k);
    for (int i = 0; i < (k << 1); i++)
      tmp[i] = i < k ? ((i == 0) - tmp[i] + A[i]) % 998244353 : 0,
      B[i] = i < k ? B[i] : 0;
    NTT(tmp, k << 1, 1), NTT(B, k << 1, 1);
    for (int i = 0; i < (k << 1); i++) B[i] = 1ll * B[i] * tmp[i] % 998244353;
    NTT(B, k << 1, -1);
    for (int i = min(n, k); i < (k << 1); i++) B[i] = 0;
  }
}
void Pow(int *A, int *B, int n, int k) {
  int lgn = lg[n - 1] + 2, len = 1 << lgn;
  for (int i = 0; i < len; i++) B[i] = i < n ? A[i] : 0;
  NTT(B, len, 1);
  for (int i = 0; i < len; i++) B[i] = Pow(B[i], k);
  NTT(B, len, -1);
}
int a[(1 << 21) + 5], b[(1 << 21) + 5];
int main() {
  int n, k, d[20] = {};
  scanf("%d%d", &n, &k);
  for (int i = 0; i < k; i++) scanf("%d", &d[i]);
  sort(d, d + k);
  for (int i = 0; i < k; i++) a[d[i] - d[0]]++;
  int tp = d[k - 1] - d[0];
  Init(n * 10);
  Pow(a, b, n / 2 * tp + 1, n / 2);
  int ans = 0;
  for (int i = 0; i < n * 5; i++)
    ans = (ans + 1ll * b[i] * b[i] % 998244353) % 998244353;
  printf("%d\n", (ans + 998244353) % 998244353);
}

```