#include <bits/stdc++.h>
using namespace std;
const int LG = 21, N = 1 << LG, Mod = 998244353;
int rev[N + 5];
inline int Power(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % Mod)
    if (b & 1) ret = 1ll * ret * a % Mod;
  return (ret);
}
inline void NTT(int* F, int n, bool inv) {
  int d = LG - __builtin_ctz(n);
  for (int i = 0; i < n; i++)
    if (i < (rev[i] >> d)) swap(F[i], F[(rev[i] >> d)]);
  for (int len = 1; len < n; len <<= 1) {
    int wn = Power(3, (Mod - 1) / (len << 1));
    if (inv) wn = Power(wn, Mod - 2);
    for (int i = 0; i < n; i += (len << 1))
      for (int j = i, w = 1; j < i + len; j++) {
        int a = 1ll * F[j + len] * w % Mod;
        F[j + len] = F[j] - a;
        F[j] += a;
        if (F[j + len] < 0) F[j + len] += Mod;
        if (F[j] >= Mod) F[j] -= Mod;
        w = 1ll * w * wn % Mod;
      }
  }
  if (inv)
    for (int i = 0, rn = Power(n, Mod - 2); i < n; i++)
      F[i] = 1ll * F[i] * rn % Mod;
}
int F1[N + 5];
int n, k, dp[LG][N], R[N];
int main() {
  for (int i = 0; i < N; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (LG - 1));
  scanf("%d%d", &n, &k);
  for (int i = 0, d; i < k; i++) scanf("%d", &d), dp[0][d] = 1;
  for (int i = 1; i < 17; i++) {
    int m = 16 * (1 << i);
    for (int j = 0; j < m; j++) F1[j] = dp[i - 1][j];
    NTT(F1, m, 0);
    for (int j = 0; j < m; j++) F1[j] = 1ll * F1[j] * F1[j] % Mod;
    NTT(F1, m, 1);
    for (int j = 0; j < m; j++) dp[i][j] = F1[j];
  }
  R[0] = 1;
  n >>= 1;
  for (int i = 0; i < LG; i++)
    if (n & (1 << i)) {
      int m = (1 << i + 1) * 16;
      for (int j = 0; j < m; j++) F1[j] = dp[i][j];
      NTT(F1, m, 0);
      NTT(R, m, 0);
      for (int j = 0; j < m; j++) R[j] = 1ll * R[j] * F1[j] % Mod;
      NTT(R, m, 1);
    }
  int tot = 0;
  for (int i = 0; i < N; i++) tot = (tot + 1ll * R[i] * R[i]) % Mod;
  return !printf("%d", tot);
}

### 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 int LG = 21, N = 1 << LG, Mod = 998244353;
int rev[N + 5];
inline int Power(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % Mod)
    if (b & 1) ret = 1ll * ret * a % Mod;
  return (ret);
}
inline void NTT(int* F, int n, bool inv) {
  int d = LG - __builtin_ctz(n);
  for (int i = 0; i < n; i++)
    if (i < (rev[i] >> d)) swap(F[i], F[(rev[i] >> d)]);
  for (int len = 1; len < n; len <<= 1) {
    int wn = Power(3, (Mod - 1) / (len << 1));
    if (inv) wn = Power(wn, Mod - 2);
    for (int i = 0; i < n; i += (len << 1))
      for (int j = i, w = 1; j < i + len; j++) {
        int a = 1ll * F[j + len] * w % Mod;
        F[j + len] = F[j] - a;
        F[j] += a;
        if (F[j + len] < 0) F[j + len] += Mod;
        if (F[j] >= Mod) F[j] -= Mod;
        w = 1ll * w * wn % Mod;
      }
  }
  if (inv)
    for (int i = 0, rn = Power(n, Mod - 2); i < n; i++)
      F[i] = 1ll * F[i] * rn % Mod;
}
int F1[N + 5];
int n, k, dp[LG][N], R[N];
int main() {
  for (int i = 0; i < N; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (LG - 1));
  scanf("%d%d", &n, &k);
  for (int i = 0, d; i < k; i++) scanf("%d", &d), dp[0][d] = 1;
  for (int i = 1; i < 17; i++) {
    int m = 16 * (1 << i);
    for (int j = 0; j < m; j++) F1[j] = dp[i - 1][j];
    NTT(F1, m, 0);
    for (int j = 0; j < m; j++) F1[j] = 1ll * F1[j] * F1[j] % Mod;
    NTT(F1, m, 1);
    for (int j = 0; j < m; j++) dp[i][j] = F1[j];
  }
  R[0] = 1;
  n >>= 1;
  for (int i = 0; i < LG; i++)
    if (n & (1 << i)) {
      int m = (1 << i + 1) * 16;
      for (int j = 0; j < m; j++) F1[j] = dp[i][j];
      NTT(F1, m, 0);
      NTT(R, m, 0);
      for (int j = 0; j < m; j++) R[j] = 1ll * R[j] * F1[j] % Mod;
      NTT(R, m, 1);
    }
  int tot = 0;
  for (int i = 0; i < N; i++) tot = (tot + 1ll * R[i] * R[i]) % Mod;
  return !printf("%d", tot);
}

```