#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct Edge {
  ll to, rev;
  long double cap;
  Edge(ll _to, long double _cap, ll _rev) {
    to = _to;
    cap = _cap;
    rev = _rev;
  }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
  G[from].push_back(Edge(to, cap, (ll)G[to].size()));
  if (revFlag) G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}
template <int mod>
struct NumberTheoreticTransform {
  vector<int> rev, rts;
  int base, max_base, root;
  NumberTheoreticTransform() : base(1), rev{0, 1}, rts{0, 1} {
    assert(mod >= 3 && mod % 2 == 1);
    auto tmp = mod - 1;
    max_base = 0;
    while (tmp % 2 == 0) tmp >>= 1, max_base++;
    root = 2;
    while (mod_pow(root, (mod - 1) >> 1) == 1) ++root;
    assert(mod_pow(root, mod - 1) == 1);
    root = mod_pow(root, (mod - 1) >> max_base);
  }
  inline int mod_pow(int x, int n) {
    int ret = 1;
    while (n > 0) {
      if (n & 1) ret = mul(ret, x);
      x = mul(x, x);
      n >>= 1;
    }
    return ret;
  }
  inline int inverse(int x) { return mod_pow(x, mod - 2); }
  inline unsigned add(unsigned x, unsigned y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
  }
  inline unsigned mul(unsigned a, unsigned b) {
    return 1ull * a * b % (unsigned long long)mod;
  }
  void ensure_base(int nbase) {
    if (nbase <= base) return;
    rev.resize(1 << nbase);
    rts.resize(1 << nbase);
    for (int i = 0; i < (1 << nbase); i++) {
      rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
    }
    assert(nbase <= max_base);
    while (base < nbase) {
      int z = mod_pow(root, 1 << (max_base - 1 - base));
      for (int i = 1 << (base - 1); i < (1 << base); i++) {
        rts[i << 1] = rts[i];
        rts[(i << 1) + 1] = mul(rts[i], z);
      }
      ++base;
    }
  }
  void ntt(vector<int> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    int zeros = __builtin_ctz(n);
    ensure_base(zeros);
    int shift = base - zeros;
    for (int i = 0; i < n; i++) {
      if (i < (rev[i] >> shift)) {
        swap(a[i], a[rev[i] >> shift]);
      }
    }
    for (int k = 1; k < n; k <<= 1) {
      for (int i = 0; i < n; i += 2 * k) {
        for (int j = 0; j < k; j++) {
          int z = mul(a[i + j + k], rts[j + k]);
          a[i + j + k] = add(a[i + j], mod - z);
          a[i + j] = add(a[i + j], z);
        }
      }
    }
  }
  vector<int> multiply(vector<int> a, vector<int> b) {
    int need = a.size() + b.size() - 1;
    int nbase = 1;
    while ((1 << nbase) < need) nbase++;
    ensure_base(nbase);
    int sz = 1 << nbase;
    a.resize(sz, 0);
    b.resize(sz, 0);
    ntt(a);
    ntt(b);
    int inv_sz = inverse(sz);
    for (int i = 0; i < sz; i++) {
      a[i] = mul(a[i], mul(b[i], inv_sz));
    }
    reverse(a.begin() + 1, a.end());
    ntt(a);
    a.resize(need);
    return a;
  }
  vector<int> pow(vector<int> a, int k) {
    if (k <= 1) return a;
    if (k & 1)
      return multiply(a, pow(a, k - 1));
    else
      return pow(multiply(a, a), k / 2);
  }
};
NumberTheoreticTransform<MOD> ntt;
void solve() {
  int n, k;
  cin >> n >> k;
  vec<int> d(k);
  vec<int> a(10, 0);
  for (int(i) = (int)(0); i < (int)(k); ++i) {
    cin >> d[i];
    a[d[i]] = 1;
  }
  a = ntt.pow(a, n / 2);
  int ans = 0;
  for (auto i : a) {
    ans = ntt.add(ans, ntt.mul(i, i));
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}

### Prompt

Your task is to create 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;
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct Edge {
  ll to, rev;
  long double cap;
  Edge(ll _to, long double _cap, ll _rev) {
    to = _to;
    cap = _cap;
    rev = _rev;
  }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
  G[from].push_back(Edge(to, cap, (ll)G[to].size()));
  if (revFlag) G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}
template <int mod>
struct NumberTheoreticTransform {
  vector<int> rev, rts;
  int base, max_base, root;
  NumberTheoreticTransform() : base(1), rev{0, 1}, rts{0, 1} {
    assert(mod >= 3 && mod % 2 == 1);
    auto tmp = mod - 1;
    max_base = 0;
    while (tmp % 2 == 0) tmp >>= 1, max_base++;
    root = 2;
    while (mod_pow(root, (mod - 1) >> 1) == 1) ++root;
    assert(mod_pow(root, mod - 1) == 1);
    root = mod_pow(root, (mod - 1) >> max_base);
  }
  inline int mod_pow(int x, int n) {
    int ret = 1;
    while (n > 0) {
      if (n & 1) ret = mul(ret, x);
      x = mul(x, x);
      n >>= 1;
    }
    return ret;
  }
  inline int inverse(int x) { return mod_pow(x, mod - 2); }
  inline unsigned add(unsigned x, unsigned y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
  }
  inline unsigned mul(unsigned a, unsigned b) {
    return 1ull * a * b % (unsigned long long)mod;
  }
  void ensure_base(int nbase) {
    if (nbase <= base) return;
    rev.resize(1 << nbase);
    rts.resize(1 << nbase);
    for (int i = 0; i < (1 << nbase); i++) {
      rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
    }
    assert(nbase <= max_base);
    while (base < nbase) {
      int z = mod_pow(root, 1 << (max_base - 1 - base));
      for (int i = 1 << (base - 1); i < (1 << base); i++) {
        rts[i << 1] = rts[i];
        rts[(i << 1) + 1] = mul(rts[i], z);
      }
      ++base;
    }
  }
  void ntt(vector<int> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    int zeros = __builtin_ctz(n);
    ensure_base(zeros);
    int shift = base - zeros;
    for (int i = 0; i < n; i++) {
      if (i < (rev[i] >> shift)) {
        swap(a[i], a[rev[i] >> shift]);
      }
    }
    for (int k = 1; k < n; k <<= 1) {
      for (int i = 0; i < n; i += 2 * k) {
        for (int j = 0; j < k; j++) {
          int z = mul(a[i + j + k], rts[j + k]);
          a[i + j + k] = add(a[i + j], mod - z);
          a[i + j] = add(a[i + j], z);
        }
      }
    }
  }
  vector<int> multiply(vector<int> a, vector<int> b) {
    int need = a.size() + b.size() - 1;
    int nbase = 1;
    while ((1 << nbase) < need) nbase++;
    ensure_base(nbase);
    int sz = 1 << nbase;
    a.resize(sz, 0);
    b.resize(sz, 0);
    ntt(a);
    ntt(b);
    int inv_sz = inverse(sz);
    for (int i = 0; i < sz; i++) {
      a[i] = mul(a[i], mul(b[i], inv_sz));
    }
    reverse(a.begin() + 1, a.end());
    ntt(a);
    a.resize(need);
    return a;
  }
  vector<int> pow(vector<int> a, int k) {
    if (k <= 1) return a;
    if (k & 1)
      return multiply(a, pow(a, k - 1));
    else
      return pow(multiply(a, a), k / 2);
  }
};
NumberTheoreticTransform<MOD> ntt;
void solve() {
  int n, k;
  cin >> n >> k;
  vec<int> d(k);
  vec<int> a(10, 0);
  for (int(i) = (int)(0); i < (int)(k); ++i) {
    cin >> d[i];
    a[d[i]] = 1;
  }
  a = ntt.pow(a, n / 2);
  int ans = 0;
  for (auto i : a) {
    ans = ntt.add(ans, ntt.mul(i, i));
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}

```