#include <bits/stdc++.h>
using namespace std;
long long aa[4000005], bb[4000005], cc[4000005];
long long const modulo = 998244353;
long long const LOGN = 22;
int g = 3;
inline long long mul(long long a, long long b) { return (a * b) % modulo; }
inline long long norm(long long a) {
  if (a >= modulo) a -= modulo;
  if (a < 0) a += modulo;
  return a;
}
inline long long binPow(long long a, long long k) {
  long long ans = 1;
  while (k > 0) {
    if (k & 1) ans = mul(ans, a);
    a = mul(a, a);
    k >>= 1;
  }
  return ans;
}
inline long long inv(long long a) { return binPow(a, modulo - 2); }
vector<long long> w[LOGN];
vector<long long> rv[LOGN];
void precalc() {
  long long wb = binPow(g, (modulo - 1) / (1 << LOGN));
  for (long long st = 0; st < LOGN - 1; st++) {
    w[st].assign(1 << st, 1);
    long long bw = binPow(wb, 1 << (LOGN - st - 1));
    long long cw = 1;
    for (long long k = 0; k < (1 << st); k++) {
      w[st][k] = cw;
      cw = mul(cw, bw);
    }
  }
  for (long long st = 0; st < LOGN; st++) {
    rv[st].assign(1 << st, 0);
    if (st == 0) {
      rv[st][0] = 0;
      continue;
    }
    long long h = (1 << (st - 1));
    for (long long k = 0; k < (1 << st); k++)
      rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
  }
}
inline void fft(long long a[4000005], long long n, bool inverse) {
  long long ln = 0;
  while ((1 << ln) < n) ln++;
  assert((1 << ln) < 4000005);
  n = (1 << ln);
  for (int i = int(0); i < int(n); i++) {
    long long ni = rv[ln][i];
    if (i < ni) swap(a[i], a[ni]);
  }
  for (long long st = 0; (1 << st) < n; st++) {
    long long len = (1 << st);
    for (long long k = 0; k < n; k += (len << 1)) {
      for (long long pos = k; pos < k + len; pos++) {
        long long l = a[pos];
        long long r = mul(a[pos + len], w[st][pos - k]);
        a[pos] = norm(l + r);
        a[pos + len] = norm(l - r);
      }
    }
  }
  if (inverse) {
    long long in = inv(n);
    for (int i = int(0); i < int(n); i++) a[i] = mul(a[i], in);
    reverse(a + 1, a + n);
  }
}
vector<long long> merge(const vector<long long>& a,
                        const vector<long long>& b) {
  int ln = 1;
  while (ln < (int((a).size()) + int((b).size()))) ln <<= 1;
  for (int i = int(0); i < int(ln); i++)
    aa[i] = (i < int((a).size()) ? a[i] : 0);
  for (int i = int(0); i < int(ln); i++)
    bb[i] = (i < int((b).size()) ? b[i] : 0);
  fft(aa, ln, false);
  fft(bb, ln, false);
  for (int i = int(0); i < int(ln); i++) cc[i] = mul(aa[i], bb[i]);
  fft(cc, ln, true);
  vector<long long> c(ln, 0);
  for (int i = int(0); i < int(int((c).size())); i++) c[i] = cc[i];
  while (int((c).size()) > 1 && c.back() == 0) c.pop_back();
  return c;
}
int main() {
  precalc();
  long long n, k;
  cin >> n >> k;
  vector<long long> origMap(10, 0);
  n /= 2;
  int d;
  for (int i = 0; i < k; ++i) {
    cin >> d;
    origMap[d] = 1ll;
  }
  while (origMap.back() == 0) origMap.pop_back();
  vector<long long> res;
  res.push_back(1);
  while (n != 0) {
    if (n & 1) {
      res = merge(res, origMap);
    }
    origMap = merge(origMap, origMap);
    n >>= 1;
  }
  long long ans = 0;
  for (size_t i = 0; i < res.size(); ++i) {
    ans += res[i] * res[i];
    ans %= modulo;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Generate 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;
long long aa[4000005], bb[4000005], cc[4000005];
long long const modulo = 998244353;
long long const LOGN = 22;
int g = 3;
inline long long mul(long long a, long long b) { return (a * b) % modulo; }
inline long long norm(long long a) {
  if (a >= modulo) a -= modulo;
  if (a < 0) a += modulo;
  return a;
}
inline long long binPow(long long a, long long k) {
  long long ans = 1;
  while (k > 0) {
    if (k & 1) ans = mul(ans, a);
    a = mul(a, a);
    k >>= 1;
  }
  return ans;
}
inline long long inv(long long a) { return binPow(a, modulo - 2); }
vector<long long> w[LOGN];
vector<long long> rv[LOGN];
void precalc() {
  long long wb = binPow(g, (modulo - 1) / (1 << LOGN));
  for (long long st = 0; st < LOGN - 1; st++) {
    w[st].assign(1 << st, 1);
    long long bw = binPow(wb, 1 << (LOGN - st - 1));
    long long cw = 1;
    for (long long k = 0; k < (1 << st); k++) {
      w[st][k] = cw;
      cw = mul(cw, bw);
    }
  }
  for (long long st = 0; st < LOGN; st++) {
    rv[st].assign(1 << st, 0);
    if (st == 0) {
      rv[st][0] = 0;
      continue;
    }
    long long h = (1 << (st - 1));
    for (long long k = 0; k < (1 << st); k++)
      rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
  }
}
inline void fft(long long a[4000005], long long n, bool inverse) {
  long long ln = 0;
  while ((1 << ln) < n) ln++;
  assert((1 << ln) < 4000005);
  n = (1 << ln);
  for (int i = int(0); i < int(n); i++) {
    long long ni = rv[ln][i];
    if (i < ni) swap(a[i], a[ni]);
  }
  for (long long st = 0; (1 << st) < n; st++) {
    long long len = (1 << st);
    for (long long k = 0; k < n; k += (len << 1)) {
      for (long long pos = k; pos < k + len; pos++) {
        long long l = a[pos];
        long long r = mul(a[pos + len], w[st][pos - k]);
        a[pos] = norm(l + r);
        a[pos + len] = norm(l - r);
      }
    }
  }
  if (inverse) {
    long long in = inv(n);
    for (int i = int(0); i < int(n); i++) a[i] = mul(a[i], in);
    reverse(a + 1, a + n);
  }
}
vector<long long> merge(const vector<long long>& a,
                        const vector<long long>& b) {
  int ln = 1;
  while (ln < (int((a).size()) + int((b).size()))) ln <<= 1;
  for (int i = int(0); i < int(ln); i++)
    aa[i] = (i < int((a).size()) ? a[i] : 0);
  for (int i = int(0); i < int(ln); i++)
    bb[i] = (i < int((b).size()) ? b[i] : 0);
  fft(aa, ln, false);
  fft(bb, ln, false);
  for (int i = int(0); i < int(ln); i++) cc[i] = mul(aa[i], bb[i]);
  fft(cc, ln, true);
  vector<long long> c(ln, 0);
  for (int i = int(0); i < int(int((c).size())); i++) c[i] = cc[i];
  while (int((c).size()) > 1 && c.back() == 0) c.pop_back();
  return c;
}
int main() {
  precalc();
  long long n, k;
  cin >> n >> k;
  vector<long long> origMap(10, 0);
  n /= 2;
  int d;
  for (int i = 0; i < k; ++i) {
    cin >> d;
    origMap[d] = 1ll;
  }
  while (origMap.back() == 0) origMap.pop_back();
  vector<long long> res;
  res.push_back(1);
  while (n != 0) {
    if (n & 1) {
      res = merge(res, origMap);
    }
    origMap = merge(origMap, origMap);
    n >>= 1;
  }
  long long ans = 0;
  for (size_t i = 0; i < res.size(); ++i) {
    ans += res[i] * res[i];
    ans %= modulo;
  }
  cout << ans << endl;
  return 0;
}

```