#include <bits/stdc++.h>
using namespace std;
int n, k, p[3000000];
int a[18][3000000], s[3000000];
long long g[30], ng[30], inv;
long long qk(long long a, int b) {
  long long t = 1;
  for (; b; b >>= 1, a = a * a % 998244353)
    if (b & 1) t = t * a % 998244353;
  return t;
}
void NTT(int *a, int n, bool t) {
  for (int i = 1, j = 0; i < n - 1; ++i) {
    for (int s = n; j ^= s >>= 1, ~j & s;)
      ;
    if (i < j) swap(a[i], a[j]);
  }
  for (int d = 0; (1 << d) < n; ++d) {
    int m = 1 << d, m2 = m << 1;
    long long _w = t == 1 ? g[d] : ng[d];
    for (int i = 0; i < n; i += m2) {
      long long w = 1;
      for (int j = 0; j < m; ++j) {
        int &A = a[i + j + m], &B = a[i + j];
        long long t = w * A % 998244353;
        A = B - t;
        if (A < 0) A += 998244353;
        B += t;
        if (B >= 998244353) B -= 998244353;
        w = w * _w % 998244353;
      }
    }
  }
  if (!t)
    for (int i = 0; i < n; ++i) a[i] = (long long)a[i] * inv % 998244353;
}
int main() {
  scanf("%d%d", &n, &k);
  int tt = 1, rr = -1;
  while (tt <= n * 9) tt <<= 1, ++rr;
  n /= 2;
  inv = qk(tt, 998244353 - 2);
  g[rr] = qk(3, (998244353 - 1) / tt);
  ng[rr] = qk(g[rr], 998244353 - 2);
  for (int i = (rr - 1); i >= (0); --i)
    g[i] = g[i + 1] * g[i + 1] % 998244353,
    ng[i] = ng[i + 1] * ng[i + 1] % 998244353;
  int nn = 0;
  while ((2 << nn) <= n) ++nn;
  for (int i = (1); i <= (k); ++i) scanf("%d", &p[i]);
  for (int i = (1); i <= (k); ++i)
    for (int j = (1); j <= (k); ++j) ++a[0][9 + p[i] - p[j]];
  NTT(a[0], tt, 1);
  for (int i = (1); i <= (nn); ++i)
    for (int j = (0); j <= (tt - 1); ++j)
      a[i][j] = (long long)a[i - 1][j] * a[i - 1][j] % 998244353;
  s[0] = 1;
  NTT(s, tt, 1);
  for (int i = (0); i <= (nn); ++i)
    if (n & (1 << i))
      for (int j = (0); j <= (tt - 1); ++j)
        s[j] = (long long)s[j] * a[i][j] % 998244353;
  NTT(s, tt, 0);
  printf("%d\n", s[n * 9]);
}

### 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 n, k, p[3000000];
int a[18][3000000], s[3000000];
long long g[30], ng[30], inv;
long long qk(long long a, int b) {
  long long t = 1;
  for (; b; b >>= 1, a = a * a % 998244353)
    if (b & 1) t = t * a % 998244353;
  return t;
}
void NTT(int *a, int n, bool t) {
  for (int i = 1, j = 0; i < n - 1; ++i) {
    for (int s = n; j ^= s >>= 1, ~j & s;)
      ;
    if (i < j) swap(a[i], a[j]);
  }
  for (int d = 0; (1 << d) < n; ++d) {
    int m = 1 << d, m2 = m << 1;
    long long _w = t == 1 ? g[d] : ng[d];
    for (int i = 0; i < n; i += m2) {
      long long w = 1;
      for (int j = 0; j < m; ++j) {
        int &A = a[i + j + m], &B = a[i + j];
        long long t = w * A % 998244353;
        A = B - t;
        if (A < 0) A += 998244353;
        B += t;
        if (B >= 998244353) B -= 998244353;
        w = w * _w % 998244353;
      }
    }
  }
  if (!t)
    for (int i = 0; i < n; ++i) a[i] = (long long)a[i] * inv % 998244353;
}
int main() {
  scanf("%d%d", &n, &k);
  int tt = 1, rr = -1;
  while (tt <= n * 9) tt <<= 1, ++rr;
  n /= 2;
  inv = qk(tt, 998244353 - 2);
  g[rr] = qk(3, (998244353 - 1) / tt);
  ng[rr] = qk(g[rr], 998244353 - 2);
  for (int i = (rr - 1); i >= (0); --i)
    g[i] = g[i + 1] * g[i + 1] % 998244353,
    ng[i] = ng[i + 1] * ng[i + 1] % 998244353;
  int nn = 0;
  while ((2 << nn) <= n) ++nn;
  for (int i = (1); i <= (k); ++i) scanf("%d", &p[i]);
  for (int i = (1); i <= (k); ++i)
    for (int j = (1); j <= (k); ++j) ++a[0][9 + p[i] - p[j]];
  NTT(a[0], tt, 1);
  for (int i = (1); i <= (nn); ++i)
    for (int j = (0); j <= (tt - 1); ++j)
      a[i][j] = (long long)a[i - 1][j] * a[i - 1][j] % 998244353;
  s[0] = 1;
  NTT(s, tt, 1);
  for (int i = (0); i <= (nn); ++i)
    if (n & (1 << i))
      for (int j = (0); j <= (tt - 1); ++j)
        s[j] = (long long)s[j] * a[i][j] % 998244353;
  NTT(s, tt, 0);
  printf("%d\n", s[n * 9]);
}

```