#include <bits/stdc++.h>
using namespace std;
template <typename num_t>
inline void addmod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void update_max(num_t& a, const num_t& b) {
  a = max(a, b);
}
template <typename num_t>
inline void update_min(num_t& a, const num_t& b) {
  a = min(a, b);
}
template <typename num_t>
num_t gcd(num_t lhs, num_t rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
const int inf = 1e9 + 7;
const int mod = 998244353;
const int MAX_N = 2000 + 7;
const long long ll_inf = 9ll * inf * inf;
const int pr[3] = {1004535809, 1007681537, 1012924417};
const int pw[3] = {3, 3, 5};
struct NTT {
  static const int MAXF = 1 << 20;
  int pr;
  int rts[MAXF + 1];
  int bitrev[MAXF];
  int iv[MAXF + 1];
  int fpow(int a, int k, int p) {
    if (!k) return 1;
    int res = a, tmp = a;
    k--;
    while (k) {
      if (k & 1) {
        res = (long long)res * tmp % p;
      }
      tmp = (long long)tmp * tmp % p;
      k >>= 1;
    }
    return res;
  }
  void init(int pr, int pw) {
    this->pr = pr;
    int k = 0;
    while ((1 << k) < MAXF) k++;
    bitrev[0] = 0;
    for (int i = 1; i < MAXF; i++) {
      bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
    }
    pw = fpow(pw, (pr - 1) / MAXF, pr);
    rts[0] = 1;
    for (int i = 1; i <= MAXF; i++) {
      rts[i] = (long long)rts[i - 1] * pw % pr;
    }
    for (int i = 1; i <= MAXF; i <<= 1) {
      iv[i] = fpow(i, pr - 2, pr);
    }
  }
  void dft(int a[], int n, int sign) {
    int d = 0;
    while ((1 << d) * n != MAXF) d++;
    for (int i = 0; i < n; i++) {
      if (i < (bitrev[i] >> d)) {
        swap(a[i], a[bitrev[i] >> d]);
      }
    }
    for (int len = 2; len <= n; len <<= 1) {
      int delta = MAXF / len * sign;
      for (int i = 0; i < n; i += len) {
        int* w = sign > 0 ? rts : rts + MAXF;
        for (int k = 0; k + k < len; k++) {
          int &a1 = a[i + k + (len >> 1)], &a2 = a[i + k];
          int t = (long long)*w * a1 % pr;
          a1 = a2 - t;
          a2 = a2 + t;
          a1 += a1 < 0 ? pr : 0;
          a2 -= a2 >= pr ? pr : 0;
          w += delta;
        }
      }
    }
    if (sign < 0) {
      int in = iv[n];
      for (int i = 0; i < n; i++) {
        a[i] = (long long)a[i] * in % pr;
      }
    }
  }
  void multiply(int a[], int b[], int na, int nb, int c[]) {
    static int fa[MAXF], fb[MAXF];
    int n = na + nb - 1;
    while (n != (n & -n)) n += n & -n;
    for (int i = 0; i < n; i++) fa[i] = fb[i] = 0;
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    dft(fa, n, 1), dft(fb, n, 1);
    for (int i = 0; i < n; i++) fa[i] = (long long)fa[i] * fb[i] % pr;
    dft(fa, n, -1);
    for (int i = 0; i < n; i++) c[i] = fa[i];
  }
  vector<int> multiply(vector<int> a, vector<int> b) {
    static int fa[MAXF], fb[MAXF], fc[MAXF];
    int na = a.size(), nb = b.size();
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    multiply(fa, fb, na, nb, fc);
    int k = na + nb - 1;
    vector<int> res(k);
    for (int i = 0; i < k; i++) res[i] = fc[i];
    return res;
  }
} ntt;
int n, k;
vector<int> d;
vector<int> pre_dp[MAX_N];
void update(vector<int>& cur, vector<int>& pre) {
  for (int i = (0), _b = ((int)(pre).size()); i < _b; ++i)
    if (pre[i]) {
      for (int x : d) {
        cur[i + x] += pre[i];
        if (cur[i + x] >= mod) cur[i + x] -= mod;
      }
    }
}
vector<int> calc(int m) {
  if (m < MAX_N) {
    return pre_dp[m];
  } else {
    auto temp = calc(m / 2);
    temp = ntt.multiply(temp, temp);
    if (m & 1) {
      vector<int> res(temp.size() + 9, 0);
      update(res, temp);
      return res;
    } else {
      return temp;
    }
  }
}
void solve() {
  ntt.init(mod, 3);
  cin >> n >> k;
  d.resize(k);
  for (int i = (0), _b = (k); i < _b; ++i) {
    cin >> d[i];
  }
  pre_dp[0] = {1};
  for (int i = (1), _b = (MAX_N); i < _b; ++i) {
    pre_dp[i].assign(pre_dp[i - 1].size() + 9, 0);
    update(pre_dp[i], pre_dp[i - 1]);
  }
  long long res = 0;
  auto r = calc(n / 2);
  for (int i = (0), _b = ((int)(r).size()); i < _b; ++i)
    addmod(res, 1ll * r[i] * r[i], mod);
  cout << res << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}

### Prompt

Please create a solution in cpp 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;
template <typename num_t>
inline void addmod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void update_max(num_t& a, const num_t& b) {
  a = max(a, b);
}
template <typename num_t>
inline void update_min(num_t& a, const num_t& b) {
  a = min(a, b);
}
template <typename num_t>
num_t gcd(num_t lhs, num_t rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
const int inf = 1e9 + 7;
const int mod = 998244353;
const int MAX_N = 2000 + 7;
const long long ll_inf = 9ll * inf * inf;
const int pr[3] = {1004535809, 1007681537, 1012924417};
const int pw[3] = {3, 3, 5};
struct NTT {
  static const int MAXF = 1 << 20;
  int pr;
  int rts[MAXF + 1];
  int bitrev[MAXF];
  int iv[MAXF + 1];
  int fpow(int a, int k, int p) {
    if (!k) return 1;
    int res = a, tmp = a;
    k--;
    while (k) {
      if (k & 1) {
        res = (long long)res * tmp % p;
      }
      tmp = (long long)tmp * tmp % p;
      k >>= 1;
    }
    return res;
  }
  void init(int pr, int pw) {
    this->pr = pr;
    int k = 0;
    while ((1 << k) < MAXF) k++;
    bitrev[0] = 0;
    for (int i = 1; i < MAXF; i++) {
      bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
    }
    pw = fpow(pw, (pr - 1) / MAXF, pr);
    rts[0] = 1;
    for (int i = 1; i <= MAXF; i++) {
      rts[i] = (long long)rts[i - 1] * pw % pr;
    }
    for (int i = 1; i <= MAXF; i <<= 1) {
      iv[i] = fpow(i, pr - 2, pr);
    }
  }
  void dft(int a[], int n, int sign) {
    int d = 0;
    while ((1 << d) * n != MAXF) d++;
    for (int i = 0; i < n; i++) {
      if (i < (bitrev[i] >> d)) {
        swap(a[i], a[bitrev[i] >> d]);
      }
    }
    for (int len = 2; len <= n; len <<= 1) {
      int delta = MAXF / len * sign;
      for (int i = 0; i < n; i += len) {
        int* w = sign > 0 ? rts : rts + MAXF;
        for (int k = 0; k + k < len; k++) {
          int &a1 = a[i + k + (len >> 1)], &a2 = a[i + k];
          int t = (long long)*w * a1 % pr;
          a1 = a2 - t;
          a2 = a2 + t;
          a1 += a1 < 0 ? pr : 0;
          a2 -= a2 >= pr ? pr : 0;
          w += delta;
        }
      }
    }
    if (sign < 0) {
      int in = iv[n];
      for (int i = 0; i < n; i++) {
        a[i] = (long long)a[i] * in % pr;
      }
    }
  }
  void multiply(int a[], int b[], int na, int nb, int c[]) {
    static int fa[MAXF], fb[MAXF];
    int n = na + nb - 1;
    while (n != (n & -n)) n += n & -n;
    for (int i = 0; i < n; i++) fa[i] = fb[i] = 0;
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    dft(fa, n, 1), dft(fb, n, 1);
    for (int i = 0; i < n; i++) fa[i] = (long long)fa[i] * fb[i] % pr;
    dft(fa, n, -1);
    for (int i = 0; i < n; i++) c[i] = fa[i];
  }
  vector<int> multiply(vector<int> a, vector<int> b) {
    static int fa[MAXF], fb[MAXF], fc[MAXF];
    int na = a.size(), nb = b.size();
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    multiply(fa, fb, na, nb, fc);
    int k = na + nb - 1;
    vector<int> res(k);
    for (int i = 0; i < k; i++) res[i] = fc[i];
    return res;
  }
} ntt;
int n, k;
vector<int> d;
vector<int> pre_dp[MAX_N];
void update(vector<int>& cur, vector<int>& pre) {
  for (int i = (0), _b = ((int)(pre).size()); i < _b; ++i)
    if (pre[i]) {
      for (int x : d) {
        cur[i + x] += pre[i];
        if (cur[i + x] >= mod) cur[i + x] -= mod;
      }
    }
}
vector<int> calc(int m) {
  if (m < MAX_N) {
    return pre_dp[m];
  } else {
    auto temp = calc(m / 2);
    temp = ntt.multiply(temp, temp);
    if (m & 1) {
      vector<int> res(temp.size() + 9, 0);
      update(res, temp);
      return res;
    } else {
      return temp;
    }
  }
}
void solve() {
  ntt.init(mod, 3);
  cin >> n >> k;
  d.resize(k);
  for (int i = (0), _b = (k); i < _b; ++i) {
    cin >> d[i];
  }
  pre_dp[0] = {1};
  for (int i = (1), _b = (MAX_N); i < _b; ++i) {
    pre_dp[i].assign(pre_dp[i - 1].size() + 9, 0);
    update(pre_dp[i], pre_dp[i - 1]);
  }
  long long res = 0;
  auto r = calc(n / 2);
  for (int i = (0), _b = ((int)(r).size()); i < _b; ++i)
    addmod(res, 1ll * r[i] * r[i], mod);
  cout << res << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}

```