#include <bits/stdc++.h>
using namespace std;
const int mod(998244353);
const int maxn(1 << 21);
inline void Inc(int &x, const int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void Dec(int &x, const int y) { x = x - y < 0 ? x - y + mod : x - y; }
inline int Add(const int x, const int y) {
  return x + y >= mod ? x + y - mod : x + y;
}
inline int Sub(const int x, const int y) {
  return x - y < 0 ? x - y + mod : x - y;
}
inline int Pow(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x % mod)
    if (y & 1) ret = ret * x % mod;
  return ret;
}
namespace NTT {
int w[2][maxn], r[maxn], l, deg;
inline void Init(int len) {
  int i, x, y;
  for (l = 0, deg = 1; deg < len; deg <<= 1) ++l;
  for (i = 0; i < deg; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  x = Pow(3, (mod - 1) / deg), y = Pow(x, mod - 2), w[0][0] = w[1][0] = 1;
  for (i = 1; i < deg; ++i)
    w[0][i] = (long long)w[0][i - 1] * x % mod,
    w[1][i] = (long long)w[1][i - 1] * y % mod;
}
inline void DFT(int *p, int opt) {
  int i, j, k, t, wn, x, y;
  for (i = 0; i < deg; ++i)
    if (r[i] < i) swap(p[r[i]], p[i]);
  for (i = 1; i < deg; i <<= 1)
    for (t = i << 1, j = 0; j < deg; j += t)
      for (k = 0; k < i; ++k) {
        wn = w[opt == -1][deg / t * k];
        x = p[j + k], y = (long long)p[j + k + i] * wn % mod;
        p[j + k] = Add(x, y), p[j + k + i] = Sub(x, y);
      }
  if (opt == -1)
    for (i = 0, wn = Pow(deg, mod - 2); i < deg; ++i)
      p[i] = (long long)p[i] * wn % mod;
}
}  // namespace NTT
using NTT ::DFT;
using NTT ::Init;
inline vector<int> operator*(const vector<int> &a, const vector<int> &b) {
  int n = a.size(), m = b.size(), l = n + m - 1, i, j, len;
  vector<int> c(l);
  if (l <= 256) {
    c.clear(), c.resize(l);
    for (i = 0; i < n; ++i)
      for (j = 0; j < m; ++j) Inc(c[i + j], (long long)a[i] * b[j] % mod);
    return c;
  }
  static int x[maxn], y[maxn];
  Init(l), len = NTT ::deg;
  for (i = 0; i < len; ++i) x[i] = y[i] = 0;
  for (i = 0; i < n; ++i) x[i] = a[i];
  for (i = 0; i < m; ++i) y[i] = b[i];
  DFT(x, 1), DFT(y, 1);
  for (i = 0; i < len; ++i) x[i] = (long long)x[i] * y[i] % mod;
  DFT(x, -1);
  for (i = 0; i < l; ++i) c[i] = x[i];
  return c;
}
int n, k, len, ans;
vector<int> f, g;
int main() {
  int i, x;
  scanf("%d%d", &n, &k);
  f.resize(10), g.resize(10), f[0] = 1;
  for (i = 0; i < k; ++i) scanf("%d", &x), g[x] = 1;
  for (x = n >> 1; x; x >>= 1, g = g * g)
    if (x & 1) f = f * g;
  for (len = f.size(), i = 0; i < len; ++i)
    Inc(ans, (long long)f[i] * f[i] % mod);
  printf("%d\n", ans);
  return 0;
}

### 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;
const int mod(998244353);
const int maxn(1 << 21);
inline void Inc(int &x, const int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void Dec(int &x, const int y) { x = x - y < 0 ? x - y + mod : x - y; }
inline int Add(const int x, const int y) {
  return x + y >= mod ? x + y - mod : x + y;
}
inline int Sub(const int x, const int y) {
  return x - y < 0 ? x - y + mod : x - y;
}
inline int Pow(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x % mod)
    if (y & 1) ret = ret * x % mod;
  return ret;
}
namespace NTT {
int w[2][maxn], r[maxn], l, deg;
inline void Init(int len) {
  int i, x, y;
  for (l = 0, deg = 1; deg < len; deg <<= 1) ++l;
  for (i = 0; i < deg; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  x = Pow(3, (mod - 1) / deg), y = Pow(x, mod - 2), w[0][0] = w[1][0] = 1;
  for (i = 1; i < deg; ++i)
    w[0][i] = (long long)w[0][i - 1] * x % mod,
    w[1][i] = (long long)w[1][i - 1] * y % mod;
}
inline void DFT(int *p, int opt) {
  int i, j, k, t, wn, x, y;
  for (i = 0; i < deg; ++i)
    if (r[i] < i) swap(p[r[i]], p[i]);
  for (i = 1; i < deg; i <<= 1)
    for (t = i << 1, j = 0; j < deg; j += t)
      for (k = 0; k < i; ++k) {
        wn = w[opt == -1][deg / t * k];
        x = p[j + k], y = (long long)p[j + k + i] * wn % mod;
        p[j + k] = Add(x, y), p[j + k + i] = Sub(x, y);
      }
  if (opt == -1)
    for (i = 0, wn = Pow(deg, mod - 2); i < deg; ++i)
      p[i] = (long long)p[i] * wn % mod;
}
}  // namespace NTT
using NTT ::DFT;
using NTT ::Init;
inline vector<int> operator*(const vector<int> &a, const vector<int> &b) {
  int n = a.size(), m = b.size(), l = n + m - 1, i, j, len;
  vector<int> c(l);
  if (l <= 256) {
    c.clear(), c.resize(l);
    for (i = 0; i < n; ++i)
      for (j = 0; j < m; ++j) Inc(c[i + j], (long long)a[i] * b[j] % mod);
    return c;
  }
  static int x[maxn], y[maxn];
  Init(l), len = NTT ::deg;
  for (i = 0; i < len; ++i) x[i] = y[i] = 0;
  for (i = 0; i < n; ++i) x[i] = a[i];
  for (i = 0; i < m; ++i) y[i] = b[i];
  DFT(x, 1), DFT(y, 1);
  for (i = 0; i < len; ++i) x[i] = (long long)x[i] * y[i] % mod;
  DFT(x, -1);
  for (i = 0; i < l; ++i) c[i] = x[i];
  return c;
}
int n, k, len, ans;
vector<int> f, g;
int main() {
  int i, x;
  scanf("%d%d", &n, &k);
  f.resize(10), g.resize(10), f[0] = 1;
  for (i = 0; i < k; ++i) scanf("%d", &x), g[x] = 1;
  for (x = n >> 1; x; x >>= 1, g = g * g)
    if (x & 1) f = f * g;
  for (len = f.size(), i = 0; i < len; ++i)
    Inc(ans, (long long)f[i] * f[i] % mod);
  printf("%d\n", ans);
  return 0;
}

```