#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long long maxn = 1 << 20;
const long long inf = 1e16;
long long n, m, k, t;
const long long mod = 998244353;
const long long root = 3;
inline long long step(long long a, long long first) {
  if (first == 0) {
    return 1;
  }
  if (first % 2 == 1) {
    return step(a, first - 1) * a % mod;
  }
  long long t = step(a, first / 2);
  return t * t % mod;
}
inline long long del(long long a, long long b) {
  return a * step(b, mod - 2) % mod;
}
long long st2[maxn];
long long rev(long long first, long long lg) {
  long long ans = 0;
  long long q;
  for (q = 0; q < lg; q++) {
    if ((first & (1 << q)) != 0) {
      ans += (1 << (lg - q - 1));
    }
  }
  return ans;
}
vector<long long> I[maxn];
void fft(vector<long long> &A, bool inv) {
  long long lg = 0, n = 1;
  while (n < A.size()) {
    n *= 2;
    lg++;
  }
  if (I[lg].empty()) {
    I[lg].resize(n);
    for (long long q = 0; q < A.size(); q++) {
      I[lg][q] = rev(q, lg);
      if (q < rev(q, lg)) {
        swap(A[q], A[rev(q, lg)]);
      }
    }
  } else {
    for (long long q = 0; q < A.size(); q++) {
      if (q < I[lg][q]) {
        swap(A[q], A[I[lg][q]]);
      }
    }
  }
  assert(n == A.size());
  for (long long len = 2; len <= n; len *= 2) {
    long long base = step(root, (mod - 1) / len);
    if (inv) {
      base = del(1, base);
    }
    for (long long q = 0; q < n; q += len) {
      long long w1 = 1;
      for (long long w = q; w < q + len / 2; w++) {
        long long x1 = (A[w] + w1 * A[w + len / 2]) % mod;
        long long x2 = (A[w] - w1 * A[w + len / 2] % mod + mod) % mod;
        A[w] = x1;
        A[w + len / 2] = x2;
        w1 *= base;
        w1 %= mod;
      }
    }
  }
  if (inv) {
    long long rn = del(1, n);
    for (long long q = 0; q < A.size(); q++) {
      A[q] = A[q] * rn % mod;
    }
  }
}
vector<long long> multiply(vector<long long> A, vector<long long> B) {
  while (!A.empty() && A.back() == 0) {
    A.pop_back();
  }
  while (!B.empty() && B.back() == 0) {
    B.pop_back();
  }
  vector<long long> A1(A.begin(), A.end()), B1(B.begin(), B.end());
  long long n = 1;
  while (n < max(A.size(), B.size())) {
    n *= 2;
  }
  n *= 2;
  A1.resize(n);
  B1.resize(n);
  fft(A1, 0);
  if (A == B) {
    B1 = A1;
  } else {
    fft(B1, 0);
  }
  for (long long q = 0; q < A1.size(); q++) {
    A1[q] = A1[q] * B1[q] % mod;
  }
  fft(A1, 1);
  vector<long long> ANS(A1.size());
  for (long long q = 0; q < A1.size(); q++) {
    ANS[q] = A1[q];
  }
  return ANS;
}
vector<long long> step(vector<long long> A, long long first) {
  if (first == 0) {
    return {1};
  }
  if (first % 2 == 1) {
    return multiply(A, step(A, first - 1));
  }
  vector<long long> T = step(A, first / 2);
  return multiply(T, T);
}
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q, w, e, a, b, c;
  cin >> n >> k;
  vector<long long> A(maxn);
  for (q = 0; q < k; q++) {
    cin >> a;
    A[a] = 1;
  }
  fft(A, 0);
  for (q = 0; q < A.size(); q++) {
    A[q] = step(A[q], n / 2);
  }
  fft(A, 1);
  long long ans = 0;
  for (q = 0; q < A.size(); q++) {
    ans += A[q] * A[q] % mod;
    ans %= mod;
  }
  cout << 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>
#pragma GCC optimize("O3")
using namespace std;
const long long maxn = 1 << 20;
const long long inf = 1e16;
long long n, m, k, t;
const long long mod = 998244353;
const long long root = 3;
inline long long step(long long a, long long first) {
  if (first == 0) {
    return 1;
  }
  if (first % 2 == 1) {
    return step(a, first - 1) * a % mod;
  }
  long long t = step(a, first / 2);
  return t * t % mod;
}
inline long long del(long long a, long long b) {
  return a * step(b, mod - 2) % mod;
}
long long st2[maxn];
long long rev(long long first, long long lg) {
  long long ans = 0;
  long long q;
  for (q = 0; q < lg; q++) {
    if ((first & (1 << q)) != 0) {
      ans += (1 << (lg - q - 1));
    }
  }
  return ans;
}
vector<long long> I[maxn];
void fft(vector<long long> &A, bool inv) {
  long long lg = 0, n = 1;
  while (n < A.size()) {
    n *= 2;
    lg++;
  }
  if (I[lg].empty()) {
    I[lg].resize(n);
    for (long long q = 0; q < A.size(); q++) {
      I[lg][q] = rev(q, lg);
      if (q < rev(q, lg)) {
        swap(A[q], A[rev(q, lg)]);
      }
    }
  } else {
    for (long long q = 0; q < A.size(); q++) {
      if (q < I[lg][q]) {
        swap(A[q], A[I[lg][q]]);
      }
    }
  }
  assert(n == A.size());
  for (long long len = 2; len <= n; len *= 2) {
    long long base = step(root, (mod - 1) / len);
    if (inv) {
      base = del(1, base);
    }
    for (long long q = 0; q < n; q += len) {
      long long w1 = 1;
      for (long long w = q; w < q + len / 2; w++) {
        long long x1 = (A[w] + w1 * A[w + len / 2]) % mod;
        long long x2 = (A[w] - w1 * A[w + len / 2] % mod + mod) % mod;
        A[w] = x1;
        A[w + len / 2] = x2;
        w1 *= base;
        w1 %= mod;
      }
    }
  }
  if (inv) {
    long long rn = del(1, n);
    for (long long q = 0; q < A.size(); q++) {
      A[q] = A[q] * rn % mod;
    }
  }
}
vector<long long> multiply(vector<long long> A, vector<long long> B) {
  while (!A.empty() && A.back() == 0) {
    A.pop_back();
  }
  while (!B.empty() && B.back() == 0) {
    B.pop_back();
  }
  vector<long long> A1(A.begin(), A.end()), B1(B.begin(), B.end());
  long long n = 1;
  while (n < max(A.size(), B.size())) {
    n *= 2;
  }
  n *= 2;
  A1.resize(n);
  B1.resize(n);
  fft(A1, 0);
  if (A == B) {
    B1 = A1;
  } else {
    fft(B1, 0);
  }
  for (long long q = 0; q < A1.size(); q++) {
    A1[q] = A1[q] * B1[q] % mod;
  }
  fft(A1, 1);
  vector<long long> ANS(A1.size());
  for (long long q = 0; q < A1.size(); q++) {
    ANS[q] = A1[q];
  }
  return ANS;
}
vector<long long> step(vector<long long> A, long long first) {
  if (first == 0) {
    return {1};
  }
  if (first % 2 == 1) {
    return multiply(A, step(A, first - 1));
  }
  vector<long long> T = step(A, first / 2);
  return multiply(T, T);
}
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q, w, e, a, b, c;
  cin >> n >> k;
  vector<long long> A(maxn);
  for (q = 0; q < k; q++) {
    cin >> a;
    A[a] = 1;
  }
  fft(A, 0);
  for (q = 0; q < A.size(); q++) {
    A[q] = step(A[q], n / 2);
  }
  fft(A, 1);
  long long ans = 0;
  for (q = 0; q < A.size(); q++) {
    ans += A[q] * A[q] % mod;
    ans %= mod;
  }
  cout << ans;
  return 0;
}

```