#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = (int)998244353;
const int N = (int)1 << 20;
int n, k;
vector<int> a;
long long Pow(long long x, long long k, long long _p) {
  long long ans = 1;
  for (; k; k >>= 1, x = x * x % _p)
    if (k & 1) (ans *= x) %= _p;
  return ans;
}
const int _M = N, _N = N;
template <class V>
struct FT {
  vector<V> aa, bb;
  int _p, K;
  V w[2][_M * 2 + 5], rev[_M * 2 + 5], tmp;
  void Init(int _K, int p) { K = _K, _p = p; }
  void FFT(vector<V>& A, int m, int op) {
    int N = 1 << m;
    V w0 = Pow(3, (_p - 1) / N, _p);
    w[0][0] = w[1][0] = 1;
    for (int i = (1); i < (N); ++i)
      w[0][i] = w[1][N - i] = (long long)w[0][i - 1] * w0 % _p;
    for (int i = (1); i < (N); ++i)
      rev[i] = (rev[i >> 1] >> 1) | (i & 1) << m - 1;
    for (int i = (0); i < (N); ++i)
      if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 1; i < N; i <<= 1)
      for (int j = 0, t = N / (i << 1); j < N; j += i << 1)
        for (int k = j, l = 0; k < j + i; k++, l += t) {
          V x = A[k], y = (long long)w[op][l] * A[k + i] % _p;
          A[k] = (x + y) % _p, A[k + i] = (x - y + _p) % _p;
        }
    if (op) {
      tmp = Pow(N, _p - 2, _p);
      for (int i = (0); i < (N); ++i) A[i] = 1ll * A[i] * tmp % _p;
    }
  }
  vector<V>& mul(vector<V>& A, vector<V>& B, vector<V>* C = NULL, int op = 0) {
    int lena = A.size(), lenb = B.size(), len = 1, L = 0;
    aa = A, bb = B;
    while (len < 2 * max(lena, lenb)) len <<= 1, ++L;
    aa.resize(len), bb.resize(len);
    if (op) reverse((bb).begin(), (bb).end());
    FFT(aa, L, 0), FFT(bb, L, 0);
    if (!C) C = &A;
    (*C).resize(len);
    for (int i = (0); i < (len); ++i) (*C)[i] = (long long)aa[i] * bb[i] % _p;
    FFT(*C, L, 1);
    if (op) reverse((*C).begin(), (*C).end());
    if (K < len - 1) (*C).resize(K + 1);
    return *C;
  }
};
FT<int> obj;
vector<int> qpow(vector<int> a, int b) {
  vector<int> r(1, 1);
  for (; b; obj.mul(a, a), b >>= 1)
    if (b & 1) obj.mul(r, a);
  return r;
}
void Init() {
  obj.Init(1000000, 998244353);
  a.resize(10);
  for (int i = (0); i < (k); ++i) {
    int x;
    scanf("%d", &x);
    a[x] = 1;
  }
}
int Solve() {
  a = qpow(a, n / 2);
  int ans = 0;
  for (auto o : a) ans = (ans + 1ll * o * o % MOD) % MOD;
  return printf("%d\n", ans);
}
int main() {
  while (~scanf("%d%d", &n, &k)) {
    Init();
    Solve();
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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 INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = (int)998244353;
const int N = (int)1 << 20;
int n, k;
vector<int> a;
long long Pow(long long x, long long k, long long _p) {
  long long ans = 1;
  for (; k; k >>= 1, x = x * x % _p)
    if (k & 1) (ans *= x) %= _p;
  return ans;
}
const int _M = N, _N = N;
template <class V>
struct FT {
  vector<V> aa, bb;
  int _p, K;
  V w[2][_M * 2 + 5], rev[_M * 2 + 5], tmp;
  void Init(int _K, int p) { K = _K, _p = p; }
  void FFT(vector<V>& A, int m, int op) {
    int N = 1 << m;
    V w0 = Pow(3, (_p - 1) / N, _p);
    w[0][0] = w[1][0] = 1;
    for (int i = (1); i < (N); ++i)
      w[0][i] = w[1][N - i] = (long long)w[0][i - 1] * w0 % _p;
    for (int i = (1); i < (N); ++i)
      rev[i] = (rev[i >> 1] >> 1) | (i & 1) << m - 1;
    for (int i = (0); i < (N); ++i)
      if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 1; i < N; i <<= 1)
      for (int j = 0, t = N / (i << 1); j < N; j += i << 1)
        for (int k = j, l = 0; k < j + i; k++, l += t) {
          V x = A[k], y = (long long)w[op][l] * A[k + i] % _p;
          A[k] = (x + y) % _p, A[k + i] = (x - y + _p) % _p;
        }
    if (op) {
      tmp = Pow(N, _p - 2, _p);
      for (int i = (0); i < (N); ++i) A[i] = 1ll * A[i] * tmp % _p;
    }
  }
  vector<V>& mul(vector<V>& A, vector<V>& B, vector<V>* C = NULL, int op = 0) {
    int lena = A.size(), lenb = B.size(), len = 1, L = 0;
    aa = A, bb = B;
    while (len < 2 * max(lena, lenb)) len <<= 1, ++L;
    aa.resize(len), bb.resize(len);
    if (op) reverse((bb).begin(), (bb).end());
    FFT(aa, L, 0), FFT(bb, L, 0);
    if (!C) C = &A;
    (*C).resize(len);
    for (int i = (0); i < (len); ++i) (*C)[i] = (long long)aa[i] * bb[i] % _p;
    FFT(*C, L, 1);
    if (op) reverse((*C).begin(), (*C).end());
    if (K < len - 1) (*C).resize(K + 1);
    return *C;
  }
};
FT<int> obj;
vector<int> qpow(vector<int> a, int b) {
  vector<int> r(1, 1);
  for (; b; obj.mul(a, a), b >>= 1)
    if (b & 1) obj.mul(r, a);
  return r;
}
void Init() {
  obj.Init(1000000, 998244353);
  a.resize(10);
  for (int i = (0); i < (k); ++i) {
    int x;
    scanf("%d", &x);
    a[x] = 1;
  }
}
int Solve() {
  a = qpow(a, n / 2);
  int ans = 0;
  for (auto o : a) ans = (ans + 1ll * o * o % MOD) % MOD;
  return printf("%d\n", ans);
}
int main() {
  while (~scanf("%d%d", &n, &k)) {
    Init();
    Solve();
  }
  return 0;
}

```