#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int A[2000005], B[2000005], r[2000005], w[2][2000005], ans, num, m, len;
int ksm(int a, int b) {
  int s = 1;
  while (b > 0) {
    if (b & 1) s = (long long)s * a % mod;
    a = (long long)a * a % mod, b >>= 1;
  }
  return s;
}
void pre() {
  w[0][1] = w[1][1] = 1;
  for (int i = 1; i <= len; i++) {
    r[i] = (r[i >> 1] >> 1) + (i & 1) * (len >> 1);
    w[0][i] = ksm(3, (mod - 1) / i);
    w[1][i] = ksm(w[0][i], mod - 2);
  }
}
void NTT(int *a, int flag) {
  for (int i = 0; i < len; i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1; i < len; i <<= 1)
    for (int j = 0; j < len; j += i + i)
      for (int r = 0, k = 1; r < i;
           r++, k = (long long)k * w[flag][i + i] % mod) {
        int x = a[j + r], y = (long long)a[i + j + r] * k % mod;
        a[j + r] = (x + y) % mod, a[i + j + r] = (x - y + mod) % mod;
      }
  int invn = ksm(len, mod - 2);
  if (flag == 1)
    for (int i = 0; i < len; i++) a[i] = (long long)a[i] * invn % mod;
}
int main() {
  scanf("%d%d", &num, &m);
  for (int i = 1, x; i <= m; i++) scanf("%d", &x), A[x] = 1;
  for (len = 1; len <= num * 5; len <<= 1)
    ;
  pre();
  NTT(A, 0);
  for (int i = 0; i <= len; i++) B[i] = ksm(A[i], num / 2);
  NTT(B, 1);
  for (int i = 0; i <= num * 5; i++)
    ans = (ans + (long long)B[i] * B[i] % mod) % mod;
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please formulate 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>
using namespace std;
const int mod = 998244353;
int A[2000005], B[2000005], r[2000005], w[2][2000005], ans, num, m, len;
int ksm(int a, int b) {
  int s = 1;
  while (b > 0) {
    if (b & 1) s = (long long)s * a % mod;
    a = (long long)a * a % mod, b >>= 1;
  }
  return s;
}
void pre() {
  w[0][1] = w[1][1] = 1;
  for (int i = 1; i <= len; i++) {
    r[i] = (r[i >> 1] >> 1) + (i & 1) * (len >> 1);
    w[0][i] = ksm(3, (mod - 1) / i);
    w[1][i] = ksm(w[0][i], mod - 2);
  }
}
void NTT(int *a, int flag) {
  for (int i = 0; i < len; i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1; i < len; i <<= 1)
    for (int j = 0; j < len; j += i + i)
      for (int r = 0, k = 1; r < i;
           r++, k = (long long)k * w[flag][i + i] % mod) {
        int x = a[j + r], y = (long long)a[i + j + r] * k % mod;
        a[j + r] = (x + y) % mod, a[i + j + r] = (x - y + mod) % mod;
      }
  int invn = ksm(len, mod - 2);
  if (flag == 1)
    for (int i = 0; i < len; i++) a[i] = (long long)a[i] * invn % mod;
}
int main() {
  scanf("%d%d", &num, &m);
  for (int i = 1, x; i <= m; i++) scanf("%d", &x), A[x] = 1;
  for (len = 1; len <= num * 5; len <<= 1)
    ;
  pre();
  NTT(A, 0);
  for (int i = 0; i <= len; i++) B[i] = ksm(A[i], num / 2);
  NTT(B, 1);
  for (int i = 0; i <= num * 5; i++)
    ans = (ans + (long long)B[i] * B[i] % mod) % mod;
  printf("%d\n", ans);
  return 0;
}

```