#include <bits/stdc++.h>
using namespace std;
const long long N = 8e6 + 7, mod = 998244353, root = 3;
long long x[N], n, m, i, j, ma, mb, inv, res, b[N], ans[N], L, R[N];
long long pow_mod(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = 1LL * x * res % mod;
    x = 1LL * x * x % mod;
    n >>= 1;
  }
  return res;
}
void ntt(long long* x, long long type) {
  for (long long i = 0; i < n; ++i)
    if (i < R[i]) swap(x[i], x[R[i]]);
  for (long long i = 1; i < n; i <<= 1) {
    long long wn = pow_mod(root, type == 1 ? (mod - 1) / (i << 1)
                                           : (mod - 1 - (mod - 1) / (i << 1)));
    for (long long p = i << 1, j = 0; j < n; j += p) {
      long long w = 1;
      for (long long k = 0; k < i; ++k, w = 1LL * wn * w % mod) {
        long long l = x[j + k], r = 1LL * x[j + k + i] * w % mod;
        x[j + k] = (l + r) % mod;
        x[j + k + i] = (l - r + mod) % mod;
      }
    }
  }
}
void fpow(long long sz) {
  ntt(ans, 1);
  ntt(x, 1);
  while (sz) {
    if (sz & 1) {
      for (long long i = 0; i < n; i++) ans[i] = 1ll * ans[i] * x[i] % mod;
    }
    for (long long i = 0; i < n; i++) x[i] = 1ll * x[i] * x[i] % mod;
    sz >>= 1;
  }
  ntt(ans, -1);
}
int32_t main() {
  ans[0] = 1;
  long long sz, k, tx;
  cin >> sz >> k;
  for (long long i = 1; i <= k; i++) {
    scanf("%d", &tx);
    x[tx] = 1;
  }
  for (m = 200000 * 9 + 7, n = 1; n <= m; n <<= 1) L++;
  for (i = 0; i < n; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << L - 1);
  fpow(sz / 2);
  long long cnt = 0;
  inv = pow_mod(n, mod - 2);
  for (long long i = 0; i < n; i++)
    cnt =
        (cnt + (ans[i] % mod * inv % mod) * (ans[i] % mod * inv % mod) % mod) %
        mod;
  cout << cnt << endl;
}

### Prompt

Please create a solution in Cpp 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 long long N = 8e6 + 7, mod = 998244353, root = 3;
long long x[N], n, m, i, j, ma, mb, inv, res, b[N], ans[N], L, R[N];
long long pow_mod(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = 1LL * x * res % mod;
    x = 1LL * x * x % mod;
    n >>= 1;
  }
  return res;
}
void ntt(long long* x, long long type) {
  for (long long i = 0; i < n; ++i)
    if (i < R[i]) swap(x[i], x[R[i]]);
  for (long long i = 1; i < n; i <<= 1) {
    long long wn = pow_mod(root, type == 1 ? (mod - 1) / (i << 1)
                                           : (mod - 1 - (mod - 1) / (i << 1)));
    for (long long p = i << 1, j = 0; j < n; j += p) {
      long long w = 1;
      for (long long k = 0; k < i; ++k, w = 1LL * wn * w % mod) {
        long long l = x[j + k], r = 1LL * x[j + k + i] * w % mod;
        x[j + k] = (l + r) % mod;
        x[j + k + i] = (l - r + mod) % mod;
      }
    }
  }
}
void fpow(long long sz) {
  ntt(ans, 1);
  ntt(x, 1);
  while (sz) {
    if (sz & 1) {
      for (long long i = 0; i < n; i++) ans[i] = 1ll * ans[i] * x[i] % mod;
    }
    for (long long i = 0; i < n; i++) x[i] = 1ll * x[i] * x[i] % mod;
    sz >>= 1;
  }
  ntt(ans, -1);
}
int32_t main() {
  ans[0] = 1;
  long long sz, k, tx;
  cin >> sz >> k;
  for (long long i = 1; i <= k; i++) {
    scanf("%d", &tx);
    x[tx] = 1;
  }
  for (m = 200000 * 9 + 7, n = 1; n <= m; n <<= 1) L++;
  for (i = 0; i < n; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << L - 1);
  fpow(sz / 2);
  long long cnt = 0;
  inv = pow_mod(n, mod - 2);
  for (long long i = 0; i < n; i++)
    cnt =
        (cnt + (ans[i] % mod * inv % mod) * (ans[i] % mod * inv % mod) % mod) %
        mod;
  cout << cnt << endl;
}

```