#include <bits/stdc++.h>
using namespace std;
#pragma optimize("-Ofast")
const int mod = 998244353;
struct num {
  int x;
  num(int x_ = 0) { x = x_; }
} G, _1[2222222], X[2222222], rot[2222222], inv[2222222];
inline bool operator<(const num x, const num y) { return x.x > y.x; }
inline num operator+(const num x, const num y) {
  int z = x.x + y.x;
  return z < mod ? num(z) : num(z - mod);
}
inline num operator-(const num x, const num y) {
  int z = x.x - y.x;
  return z >= 0 ? num(z) : num(z + mod);
}
inline num operator*(const num x, const num y) {
  return num((long long)x.x * y.x % mod);
}
inline num operator*(const int x, const num y) {
  return num((long long)x * y.x % mod);
}
inline num operator^(num x, int y) {
  num z = num(1);
  while (y) {
    if (y & 1) {
      z = z * x;
    }
    x = x * x;
    y >>= 1;
  }
  return z;
}
void _(int n) {
  inv[1] = num(1);
  for (int i = 2; i <= n; i++) {
    inv[i] = (mod - mod / i) * inv[mod % i];
  }
  for (int i = 2; i <= n; i <<= 1) {
    rot[i] = G ^ ((mod - 1) / i);
  }
}
void rader(num x[], int n) {
  int i, j = 0, k;
  for (register int i = 0; i != n; i++) {
    if (i > j) {
      swap(x[i], x[j]);
    }
    k = n >> 1;
    while ((j ^= k) < k) {
      k >>= 1;
    }
  }
}
void NTT(num x[], int n, int o) {
  int k;
  num r, u, v, w;
  rader(x, n);
  for (int l = 2; l <= n; l <<= 1) {
    k = l >> 1;
    r = rot[l];
    for (int i = 0; i < n; i += l) {
      w = num(1);
      for (register int j = i; j < i + k; j++) {
        u = x[j];
        v = x[j + k] * w;
        x[j] = u + v;
        x[j + k] = u - v;
        w = w * r;
      }
    }
  }
  if (o == -1) {
    for (register int i = 0; i < n; i++) {
      x[i] = x[i] * inv[n];
    }
    for (register int i = 1; i < (n >> 1); i++) {
      swap(x[i], x[n - i]);
    }
  }
}
int main() {
  int n, k, z[11], oo[11] = {0};
  G = num(3);
  scanf("%d%d", &n, &k);
  n /= 2;
  for (int i = 1; i <= k; i++) {
    scanf("%d", &z[i]);
    oo[z[i]] = 1;
  }
  for (int i = 0; i <= 9; i++) {
    if (oo[i]) {
      _1[i] = num(1);
    }
  }
  int xxx = n;
  n *= 10;
  int S = 1;
  while (S <= n) {
    S <<= 1;
  }
  S <<= 1;
  _(S);
  X[0] = num(1);
  NTT(_1, S, 1);
  NTT(X, S, 1);
  while (xxx) {
    if (xxx & 1) {
      for (register int i = 0; i < S; i++) {
        X[i] = X[i] * _1[i];
      }
    }
    for (register int i = 0; i < S; i++) {
      _1[i] = _1[i] * _1[i];
    }
    xxx >>= 1;
  }
  NTT(X, S, -1);
  num ans = num(0);
  for (int i = 0; i <= S; i++) {
    ans = ans + (X[i] * X[i]);
  }
  printf("%d", ans.x);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
#pragma optimize("-Ofast")
const int mod = 998244353;
struct num {
  int x;
  num(int x_ = 0) { x = x_; }
} G, _1[2222222], X[2222222], rot[2222222], inv[2222222];
inline bool operator<(const num x, const num y) { return x.x > y.x; }
inline num operator+(const num x, const num y) {
  int z = x.x + y.x;
  return z < mod ? num(z) : num(z - mod);
}
inline num operator-(const num x, const num y) {
  int z = x.x - y.x;
  return z >= 0 ? num(z) : num(z + mod);
}
inline num operator*(const num x, const num y) {
  return num((long long)x.x * y.x % mod);
}
inline num operator*(const int x, const num y) {
  return num((long long)x * y.x % mod);
}
inline num operator^(num x, int y) {
  num z = num(1);
  while (y) {
    if (y & 1) {
      z = z * x;
    }
    x = x * x;
    y >>= 1;
  }
  return z;
}
void _(int n) {
  inv[1] = num(1);
  for (int i = 2; i <= n; i++) {
    inv[i] = (mod - mod / i) * inv[mod % i];
  }
  for (int i = 2; i <= n; i <<= 1) {
    rot[i] = G ^ ((mod - 1) / i);
  }
}
void rader(num x[], int n) {
  int i, j = 0, k;
  for (register int i = 0; i != n; i++) {
    if (i > j) {
      swap(x[i], x[j]);
    }
    k = n >> 1;
    while ((j ^= k) < k) {
      k >>= 1;
    }
  }
}
void NTT(num x[], int n, int o) {
  int k;
  num r, u, v, w;
  rader(x, n);
  for (int l = 2; l <= n; l <<= 1) {
    k = l >> 1;
    r = rot[l];
    for (int i = 0; i < n; i += l) {
      w = num(1);
      for (register int j = i; j < i + k; j++) {
        u = x[j];
        v = x[j + k] * w;
        x[j] = u + v;
        x[j + k] = u - v;
        w = w * r;
      }
    }
  }
  if (o == -1) {
    for (register int i = 0; i < n; i++) {
      x[i] = x[i] * inv[n];
    }
    for (register int i = 1; i < (n >> 1); i++) {
      swap(x[i], x[n - i]);
    }
  }
}
int main() {
  int n, k, z[11], oo[11] = {0};
  G = num(3);
  scanf("%d%d", &n, &k);
  n /= 2;
  for (int i = 1; i <= k; i++) {
    scanf("%d", &z[i]);
    oo[z[i]] = 1;
  }
  for (int i = 0; i <= 9; i++) {
    if (oo[i]) {
      _1[i] = num(1);
    }
  }
  int xxx = n;
  n *= 10;
  int S = 1;
  while (S <= n) {
    S <<= 1;
  }
  S <<= 1;
  _(S);
  X[0] = num(1);
  NTT(_1, S, 1);
  NTT(X, S, 1);
  while (xxx) {
    if (xxx & 1) {
      for (register int i = 0; i < S; i++) {
        X[i] = X[i] * _1[i];
      }
    }
    for (register int i = 0; i < S; i++) {
      _1[i] = _1[i] * _1[i];
    }
    xxx >>= 1;
  }
  NTT(X, S, -1);
  num ans = num(0);
  for (int i = 0; i <= S; i++) {
    ans = ans + (X[i] * X[i]);
  }
  printf("%d", ans.x);
  return 0;
}

```