#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const long long mod = 998244353;
const long long prr = 3;
int N, M, K;
long long ipow(long long a, long long x) {
  long long ret = 1;
  a %= mod;
  while (x) {
    if (x & 1) ret = ret * a % mod;
    x >>= 1;
    a = a * a % mod;
  }
  return ret;
}
namespace fft {
void fft(vector<long long> &a, bool inv) {
  int n = a.size(), j = 0;
  vector<long long> roots(n / 2);
  for (int i = 1; i < n; i++) {
    int bit = (n >> 1);
    while (j >= bit) {
      j -= bit;
      bit >>= 1;
    }
    j += bit;
    if (i < j) swap(a[i], a[j]);
  }
  long long ang = ipow(prr, (mod - 1) / n);
  if (inv) ang = ipow(ang, mod - 2);
  for (int i = 0; i < n / 2; i++) {
    roots[i] = (i ? (roots[i - 1] * ang % mod) : 1);
  }
  for (int i = 2; i <= n; i <<= 1) {
    int step = n / i;
    for (int j = 0; j < n; j += i) {
      for (int k = 0; k < i / 2; k++) {
        long long u = a[j + k], v = a[j + k + i / 2] * roots[step * k] % mod;
        a[j + k] = (u + v) % mod;
        a[j + k + i / 2] = ((u - v) % mod + mod) % mod;
      }
    }
  }
  int divn = ipow(n, mod - 2);
  if (inv)
    for (int i = 0; i < n; i++) a[i] = a[i] * divn % mod;
}
vector<long long> gv(vector<long long> &v, int N) {
  vector<long long> fv(v.begin(), v.end());
  int n = 2;
  while (n < v.size()) n <<= 1;
  fv.resize(n);
  fft(fv, 0);
  for (int i = 0; i < n; i++) fv[i] = ipow(fv[i], N);
  fft(fv, 1);
  return fv;
}
};  // namespace fft
vector<long long> dp, step;
bool can_use[10];
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 0, x; i < K; i++) {
    scanf("%d", &x);
    can_use[x] = 1;
  }
  for (int i = 0; i <= 9; i++) {
    step.push_back(can_use[i]);
  }
  step.resize(2000005);
  N /= 2;
  dp = fft::gv(step, N);
  long long ans = 0;
  for (int i = 0; i < dp.size(); i++) {
    ans += dp[i] * dp[i];
    ans %= mod;
  }
  printf("%lld", ans);
}

### Prompt

In Cpp, your task is to solve 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 double PI = acos(-1);
const long long mod = 998244353;
const long long prr = 3;
int N, M, K;
long long ipow(long long a, long long x) {
  long long ret = 1;
  a %= mod;
  while (x) {
    if (x & 1) ret = ret * a % mod;
    x >>= 1;
    a = a * a % mod;
  }
  return ret;
}
namespace fft {
void fft(vector<long long> &a, bool inv) {
  int n = a.size(), j = 0;
  vector<long long> roots(n / 2);
  for (int i = 1; i < n; i++) {
    int bit = (n >> 1);
    while (j >= bit) {
      j -= bit;
      bit >>= 1;
    }
    j += bit;
    if (i < j) swap(a[i], a[j]);
  }
  long long ang = ipow(prr, (mod - 1) / n);
  if (inv) ang = ipow(ang, mod - 2);
  for (int i = 0; i < n / 2; i++) {
    roots[i] = (i ? (roots[i - 1] * ang % mod) : 1);
  }
  for (int i = 2; i <= n; i <<= 1) {
    int step = n / i;
    for (int j = 0; j < n; j += i) {
      for (int k = 0; k < i / 2; k++) {
        long long u = a[j + k], v = a[j + k + i / 2] * roots[step * k] % mod;
        a[j + k] = (u + v) % mod;
        a[j + k + i / 2] = ((u - v) % mod + mod) % mod;
      }
    }
  }
  int divn = ipow(n, mod - 2);
  if (inv)
    for (int i = 0; i < n; i++) a[i] = a[i] * divn % mod;
}
vector<long long> gv(vector<long long> &v, int N) {
  vector<long long> fv(v.begin(), v.end());
  int n = 2;
  while (n < v.size()) n <<= 1;
  fv.resize(n);
  fft(fv, 0);
  for (int i = 0; i < n; i++) fv[i] = ipow(fv[i], N);
  fft(fv, 1);
  return fv;
}
};  // namespace fft
vector<long long> dp, step;
bool can_use[10];
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 0, x; i < K; i++) {
    scanf("%d", &x);
    can_use[x] = 1;
  }
  for (int i = 0; i <= 9; i++) {
    step.push_back(can_use[i]);
  }
  step.resize(2000005);
  N /= 2;
  dp = fft::gv(step, N);
  long long ans = 0;
  for (int i = 0; i < dp.size(); i++) {
    ans += dp[i] * dp[i];
    ans %= mod;
  }
  printf("%lld", ans);
}

```