#include <bits/stdc++.h>
using namespace std;
const int mod = 119 << 23 | 1;
namespace fft {
struct cp {
  double x, y;
  cp() { x = y = 0; }
  cp(double x, double y) : x(x), y(y) {}
};
inline cp operator+(cp a, cp b) { return cp(a.x + b.x, a.y + b.y); }
inline cp operator-(cp a, cp b) { return cp(a.x - b.x, a.y - b.y); }
inline cp operator*(cp a, cp b) {
  return cp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline cp conj(cp a) { return cp(a.x, -a.y); }
int base = 1;
vector<cp> roots = {{0, 0}, {1, 0}};
vector<int> rev = {0, 1};
const double PI = acosl(-1.0);
void ensure_base(int nbase) {
  if (nbase <= base) {
    return;
  }
  rev.resize(static_cast<unsigned long>(1 << nbase));
  for (int i = 0; i < (1 << nbase); i++) {
    rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  }
  roots.resize(static_cast<unsigned long>(1 << nbase));
  while (base < nbase) {
    double angle = 2 * PI / (1 << (base + 1));
    for (int i = 1 << (base - 1); i < (1 << base); i++) {
      roots[i << 1] = roots[i];
      double angle_i = angle * (2 * i + 1 - (1 << base));
      roots[(i << 1) + 1] = cp(cos(angle_i), sin(angle_i));
    }
    base++;
  }
}
void fft(vector<cp>& a, int n = -1) {
  if (n == -1) {
    n = 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++) {
        cp z = a[i + j + k] * roots[j + k];
        a[i + j + k] = a[i + j] - z;
        a[i + j] = a[i + j] + z;
      }
    }
  }
}
vector<cp> fa, fb;
vector<int> multiply(vector<int>& a, vector<int>& b) {
  int need = a.size() + b.size() - 1;
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  if (sz > (int)fa.size()) fa.resize(static_cast<unsigned long>(sz));
  for (int i = 0; i < sz; i++) {
    int x = (i < (int)a.size() ? a[i] : 0);
    int y = (i < (int)b.size() ? b[i] : 0);
    fa[i] = cp(x, y);
  }
  fft(fa, sz);
  cp r(0, -0.25 / sz);
  for (int i = 0; i <= (sz >> 1); i++) {
    int j = (sz - i) & (sz - 1);
    cp z = (fa[j] * fa[j] - conj(fa[i] * fa[i])) * r;
    if (i != j) {
      fa[j] = (fa[i] * fa[i] - conj(fa[j] * fa[j])) * r;
    }
    fa[i] = z;
  }
  fft(fa, sz);
  vector<int> res(static_cast<unsigned long>(need));
  for (int i = 0; i < need; i++) {
    res[i] = fa[i].x + 0.5;
  }
  return res;
}
vector<int> multiply_mod(vector<int>& a, vector<int>& b, int m, int eq = 0) {
  int need = a.size() + b.size() - 1;
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  if (sz > (int)fa.size()) {
    fa.resize(static_cast<unsigned long>(sz));
  }
  for (int i = 0; i < (int)a.size(); i++) {
    int x = (a[i] % m + m) % m;
    fa[i] = cp(x & ((1 << 15) - 1), x >> 15);
  }
  fill(fa.begin() + a.size(), fa.begin() + sz, cp{0, 0});
  fft(fa, sz);
  if (sz > (int)fb.size()) {
    fb.resize(static_cast<unsigned long>(sz));
  }
  if (eq) {
    copy(fa.begin(), fa.begin() + sz, fb.begin());
  } else {
    for (int i = 0; i < (int)b.size(); i++) {
      int x = (b[i] % m + m) % m;
      fb[i] = cp(x & ((1 << 15) - 1), x >> 15);
    }
    fill(fb.begin() + b.size(), fb.begin() + sz, cp{0, 0});
    fft(fb, sz);
  }
  double ratio = 0.25 / sz;
  cp r2(0, -1);
  cp r3(ratio, 0);
  cp r4(0, -ratio);
  cp r5(0, 1);
  for (int i = 0; i <= (sz >> 1); i++) {
    int j = (sz - i) & (sz - 1);
    cp a1 = (fa[i] + conj(fa[j]));
    cp a2 = (fa[i] - conj(fa[j])) * r2;
    cp b1 = (fb[i] + conj(fb[j])) * r3;
    cp b2 = (fb[i] - conj(fb[j])) * r4;
    if (i != j) {
      cp c1 = (fa[j] + conj(fa[i]));
      cp c2 = (fa[j] - conj(fa[i])) * r2;
      cp d1 = (fb[j] + conj(fb[i])) * r3;
      cp d2 = (fb[j] - conj(fb[i])) * r4;
      fa[i] = c1 * d1 + c2 * d2 * r5;
      fb[i] = c1 * d2 + c2 * d1;
    }
    fa[j] = a1 * b1 + a2 * b2 * r5;
    fb[j] = a1 * b2 + a2 * b1;
  }
  fft(fa, sz);
  fft(fb, sz);
  vector<int> res(static_cast<unsigned long>(need));
  for (int i = 0; i < need; i++) {
    long long aa = fa[i].x + 0.5;
    long long bb = fb[i].x + 0.5;
    long long cc = fa[i].y + 0.5;
    res[i] = (aa + ((bb % m) << 15) + ((cc % m) << 30)) % m;
  }
  return res;
}
vector<int> square(vector<int>& a) { return multiply(a, a); }
vector<int> square_mod(vector<int>& a, int m) {
  return multiply_mod(a, a, m, 1);
}
vector<int> kiss_me(vector<int>& b, long long k, int mod) {
  vector<int> a = b;
  vector<int> res(1, 1);
  for (; k; k >>= 1, a = square_mod(a, mod)) {
    if (k & 1) {
      res = multiply_mod(res, a, mod);
    }
  }
  return res;
}
pair<vector<int>, vector<int> > mul2(vector<int>& b, long long k) {
  return make_pair(kiss_me(b, k, (int)1e9 + 7), kiss_me(b, k, (int)1e9 + 9));
}
vector<vector<int> > muln(vector<int>& b, long long k, vector<int> mod_list) {
  vector<vector<int> > res(mod_list.size());
  for (int i = 0; i < mod_list.size(); ++i) {
    res[i] = kiss_me(b, k, mod_list[i]);
  }
  return res;
}
};  // namespace fft
int main() {
  ios::sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(10);
  for (int i = 0, x; i < k; i++) {
    cin >> x;
    a[x] = 1;
  }
  n >>= 1;
  vector<int> t(1);
  t[0] = 1;
  for (; n; n >>= 1, a = fft::multiply_mod(a, a, mod))
    if (n & 1) t = fft::multiply_mod(t, a, mod);
  long long ans = 0;
  for (auto& c : t) ans = (ans + 1LL * c * c % mod) % mod;
  cout << ans << endl;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 mod = 119 << 23 | 1;
namespace fft {
struct cp {
  double x, y;
  cp() { x = y = 0; }
  cp(double x, double y) : x(x), y(y) {}
};
inline cp operator+(cp a, cp b) { return cp(a.x + b.x, a.y + b.y); }
inline cp operator-(cp a, cp b) { return cp(a.x - b.x, a.y - b.y); }
inline cp operator*(cp a, cp b) {
  return cp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline cp conj(cp a) { return cp(a.x, -a.y); }
int base = 1;
vector<cp> roots = {{0, 0}, {1, 0}};
vector<int> rev = {0, 1};
const double PI = acosl(-1.0);
void ensure_base(int nbase) {
  if (nbase <= base) {
    return;
  }
  rev.resize(static_cast<unsigned long>(1 << nbase));
  for (int i = 0; i < (1 << nbase); i++) {
    rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  }
  roots.resize(static_cast<unsigned long>(1 << nbase));
  while (base < nbase) {
    double angle = 2 * PI / (1 << (base + 1));
    for (int i = 1 << (base - 1); i < (1 << base); i++) {
      roots[i << 1] = roots[i];
      double angle_i = angle * (2 * i + 1 - (1 << base));
      roots[(i << 1) + 1] = cp(cos(angle_i), sin(angle_i));
    }
    base++;
  }
}
void fft(vector<cp>& a, int n = -1) {
  if (n == -1) {
    n = 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++) {
        cp z = a[i + j + k] * roots[j + k];
        a[i + j + k] = a[i + j] - z;
        a[i + j] = a[i + j] + z;
      }
    }
  }
}
vector<cp> fa, fb;
vector<int> multiply(vector<int>& a, vector<int>& b) {
  int need = a.size() + b.size() - 1;
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  if (sz > (int)fa.size()) fa.resize(static_cast<unsigned long>(sz));
  for (int i = 0; i < sz; i++) {
    int x = (i < (int)a.size() ? a[i] : 0);
    int y = (i < (int)b.size() ? b[i] : 0);
    fa[i] = cp(x, y);
  }
  fft(fa, sz);
  cp r(0, -0.25 / sz);
  for (int i = 0; i <= (sz >> 1); i++) {
    int j = (sz - i) & (sz - 1);
    cp z = (fa[j] * fa[j] - conj(fa[i] * fa[i])) * r;
    if (i != j) {
      fa[j] = (fa[i] * fa[i] - conj(fa[j] * fa[j])) * r;
    }
    fa[i] = z;
  }
  fft(fa, sz);
  vector<int> res(static_cast<unsigned long>(need));
  for (int i = 0; i < need; i++) {
    res[i] = fa[i].x + 0.5;
  }
  return res;
}
vector<int> multiply_mod(vector<int>& a, vector<int>& b, int m, int eq = 0) {
  int need = a.size() + b.size() - 1;
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  if (sz > (int)fa.size()) {
    fa.resize(static_cast<unsigned long>(sz));
  }
  for (int i = 0; i < (int)a.size(); i++) {
    int x = (a[i] % m + m) % m;
    fa[i] = cp(x & ((1 << 15) - 1), x >> 15);
  }
  fill(fa.begin() + a.size(), fa.begin() + sz, cp{0, 0});
  fft(fa, sz);
  if (sz > (int)fb.size()) {
    fb.resize(static_cast<unsigned long>(sz));
  }
  if (eq) {
    copy(fa.begin(), fa.begin() + sz, fb.begin());
  } else {
    for (int i = 0; i < (int)b.size(); i++) {
      int x = (b[i] % m + m) % m;
      fb[i] = cp(x & ((1 << 15) - 1), x >> 15);
    }
    fill(fb.begin() + b.size(), fb.begin() + sz, cp{0, 0});
    fft(fb, sz);
  }
  double ratio = 0.25 / sz;
  cp r2(0, -1);
  cp r3(ratio, 0);
  cp r4(0, -ratio);
  cp r5(0, 1);
  for (int i = 0; i <= (sz >> 1); i++) {
    int j = (sz - i) & (sz - 1);
    cp a1 = (fa[i] + conj(fa[j]));
    cp a2 = (fa[i] - conj(fa[j])) * r2;
    cp b1 = (fb[i] + conj(fb[j])) * r3;
    cp b2 = (fb[i] - conj(fb[j])) * r4;
    if (i != j) {
      cp c1 = (fa[j] + conj(fa[i]));
      cp c2 = (fa[j] - conj(fa[i])) * r2;
      cp d1 = (fb[j] + conj(fb[i])) * r3;
      cp d2 = (fb[j] - conj(fb[i])) * r4;
      fa[i] = c1 * d1 + c2 * d2 * r5;
      fb[i] = c1 * d2 + c2 * d1;
    }
    fa[j] = a1 * b1 + a2 * b2 * r5;
    fb[j] = a1 * b2 + a2 * b1;
  }
  fft(fa, sz);
  fft(fb, sz);
  vector<int> res(static_cast<unsigned long>(need));
  for (int i = 0; i < need; i++) {
    long long aa = fa[i].x + 0.5;
    long long bb = fb[i].x + 0.5;
    long long cc = fa[i].y + 0.5;
    res[i] = (aa + ((bb % m) << 15) + ((cc % m) << 30)) % m;
  }
  return res;
}
vector<int> square(vector<int>& a) { return multiply(a, a); }
vector<int> square_mod(vector<int>& a, int m) {
  return multiply_mod(a, a, m, 1);
}
vector<int> kiss_me(vector<int>& b, long long k, int mod) {
  vector<int> a = b;
  vector<int> res(1, 1);
  for (; k; k >>= 1, a = square_mod(a, mod)) {
    if (k & 1) {
      res = multiply_mod(res, a, mod);
    }
  }
  return res;
}
pair<vector<int>, vector<int> > mul2(vector<int>& b, long long k) {
  return make_pair(kiss_me(b, k, (int)1e9 + 7), kiss_me(b, k, (int)1e9 + 9));
}
vector<vector<int> > muln(vector<int>& b, long long k, vector<int> mod_list) {
  vector<vector<int> > res(mod_list.size());
  for (int i = 0; i < mod_list.size(); ++i) {
    res[i] = kiss_me(b, k, mod_list[i]);
  }
  return res;
}
};  // namespace fft
int main() {
  ios::sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(10);
  for (int i = 0, x; i < k; i++) {
    cin >> x;
    a[x] = 1;
  }
  n >>= 1;
  vector<int> t(1);
  t[0] = 1;
  for (; n; n >>= 1, a = fft::multiply_mod(a, a, mod))
    if (n & 1) t = fft::multiply_mod(t, a, mod);
  long long ans = 0;
  for (auto& c : t) ans = (ans + 1LL * c * c % mod) % mod;
  cout << ans << endl;
}

```