#include <bits/stdc++.h>
int pi = acos(-1);
const int G = 3;
inline int inp() {
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  int sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum;
}
long long powmod(long long a, int b) {
  long long sum = 1;
  while (b) {
    if (b & 1) {
      sum *= a;
      sum %= 998244353;
    }
    a *= a;
    a %= 998244353;
    b >>= 1;
  }
  return sum;
}
int g[8000010], num[8000010];
int len, r[8000010];
int a[8000010], b[8000010], c[8000010];
int wn[8000010];
int invlim;
inline void ntt(int *a, int f) {
  for (int i = 0; i < len; i++)
    if (i < r[i]) std::swap(a[i], a[r[i]]);
  for (int i = 1; i < len; i <<= 1) {
    wn[0] = 1;
    wn[1] = powmod(G, (998244353 - 1) / (i << 1));
    for (int j = 2; j < i; j++)
      wn[j] = ((long long)(wn[j - 1]) * (long long)(wn[1]) % 998244353);
    for (int j = 0; j < len; j += i << 1) {
      int *L = a + j;
      int *R = L + i;
      for (int k = 0; k < i; k++) {
        const int t = ((long long)(wn[k]) * (long long)(R[k]) % 998244353);
        R[k] = ((L[k]) < (t) ? (L[k]) - (t) + 998244353 : (L[k]) - (t));
        L[k] =
            ((L[k]) + (t) >= 998244353 ? (L[k]) + (t)-998244353 : (L[k]) + (t));
      }
    }
  }
  if (f == -1) {
    std::reverse(a + 1, a + len);
    for (int i = 0; i < len; i++)
      a[i] = ((long long)(a[i]) * (long long)(invlim) % 998244353);
  }
}
void init(int n) {
  len = 1;
  int lg = 0;
  while (len <= n) len <<= 1, lg++;
  for (int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  invlim = powmod(len, 998244353 - 2);
}
int main() {
  int n = inp() >> 1;
  int k = inp();
  memset(g, 0, sizeof(g));
  for (int i = 1; i <= k; i++) {
    int x = inp();
    g[x] = 1;
  }
  int pownum = n - 1;
  memcpy(num, g, sizeof(g));
  init(20);
  while (pownum) {
    if (pownum & 1) {
      int maxw = 0;
      for (int i = 1; i <= 5000000; i++)
        if (g[i] > 0) maxw = i;
      init(maxw << 2);
      ntt(g, 1);
      ntt(num, 1);
      for (int i = 0; i <= len; i++)
        num[i] = ((long long)(num[i]) * (long long)(g[i]) % 998244353);
      ntt(g, -1);
      ntt(num, -1);
    }
    int maxw = 0;
    for (int i = 1; i <= 5000000; i++)
      if (g[i] > 0) maxw = i;
    init(maxw << 2);
    ntt(g, 1);
    for (int i = 0; i <= len; i++)
      g[i] = ((long long)(g[i]) * (long long)(g[i]) % 998244353);
    ntt(g, -1);
    pownum >>= 1;
  }
  int ans = 0;
  for (int i = 0; i <= len; i++)
    ans = ((ans) + (((long long)(num[i]) * (long long)(num[i]) % 998244353)) >=
                   998244353
               ? (ans) +
                     (((long long)(num[i]) * (long long)(num[i]) % 998244353)) -
                     998244353
               : (ans) +
                     (((long long)(num[i]) * (long long)(num[i]) % 998244353)));
  printf("%d\n", ans);
}

### Prompt

Your task is to create 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>
int pi = acos(-1);
const int G = 3;
inline int inp() {
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  int sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum;
}
long long powmod(long long a, int b) {
  long long sum = 1;
  while (b) {
    if (b & 1) {
      sum *= a;
      sum %= 998244353;
    }
    a *= a;
    a %= 998244353;
    b >>= 1;
  }
  return sum;
}
int g[8000010], num[8000010];
int len, r[8000010];
int a[8000010], b[8000010], c[8000010];
int wn[8000010];
int invlim;
inline void ntt(int *a, int f) {
  for (int i = 0; i < len; i++)
    if (i < r[i]) std::swap(a[i], a[r[i]]);
  for (int i = 1; i < len; i <<= 1) {
    wn[0] = 1;
    wn[1] = powmod(G, (998244353 - 1) / (i << 1));
    for (int j = 2; j < i; j++)
      wn[j] = ((long long)(wn[j - 1]) * (long long)(wn[1]) % 998244353);
    for (int j = 0; j < len; j += i << 1) {
      int *L = a + j;
      int *R = L + i;
      for (int k = 0; k < i; k++) {
        const int t = ((long long)(wn[k]) * (long long)(R[k]) % 998244353);
        R[k] = ((L[k]) < (t) ? (L[k]) - (t) + 998244353 : (L[k]) - (t));
        L[k] =
            ((L[k]) + (t) >= 998244353 ? (L[k]) + (t)-998244353 : (L[k]) + (t));
      }
    }
  }
  if (f == -1) {
    std::reverse(a + 1, a + len);
    for (int i = 0; i < len; i++)
      a[i] = ((long long)(a[i]) * (long long)(invlim) % 998244353);
  }
}
void init(int n) {
  len = 1;
  int lg = 0;
  while (len <= n) len <<= 1, lg++;
  for (int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  invlim = powmod(len, 998244353 - 2);
}
int main() {
  int n = inp() >> 1;
  int k = inp();
  memset(g, 0, sizeof(g));
  for (int i = 1; i <= k; i++) {
    int x = inp();
    g[x] = 1;
  }
  int pownum = n - 1;
  memcpy(num, g, sizeof(g));
  init(20);
  while (pownum) {
    if (pownum & 1) {
      int maxw = 0;
      for (int i = 1; i <= 5000000; i++)
        if (g[i] > 0) maxw = i;
      init(maxw << 2);
      ntt(g, 1);
      ntt(num, 1);
      for (int i = 0; i <= len; i++)
        num[i] = ((long long)(num[i]) * (long long)(g[i]) % 998244353);
      ntt(g, -1);
      ntt(num, -1);
    }
    int maxw = 0;
    for (int i = 1; i <= 5000000; i++)
      if (g[i] > 0) maxw = i;
    init(maxw << 2);
    ntt(g, 1);
    for (int i = 0; i <= len; i++)
      g[i] = ((long long)(g[i]) * (long long)(g[i]) % 998244353);
    ntt(g, -1);
    pownum >>= 1;
  }
  int ans = 0;
  for (int i = 0; i <= len; i++)
    ans = ((ans) + (((long long)(num[i]) * (long long)(num[i]) % 998244353)) >=
                   998244353
               ? (ans) +
                     (((long long)(num[i]) * (long long)(num[i]) % 998244353)) -
                     998244353
               : (ans) +
                     (((long long)(num[i]) * (long long)(num[i]) % 998244353)));
  printf("%d\n", ans);
}

```