#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const long long INF64 = 1e18;
const double INF = 1e9 + 63;
const long long mod = 998244353;
const int maxn = 3e3 + 79;
const long long sigma = 27;
const double pi = acos(-1);
long long bin_pow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      res %= mod;
    }
    a *= a;
    a %= mod;
    b >>= 1;
  }
  return res;
}
template <int mod, int root, int rootPw>
struct FFT {
 private:
  long long mul(long long a, long long b) { return (a * b) % mod; }
  long long bin_pow(long long a, long long b) {
    long long res = 1;
    while (b) {
      if (b & 1) {
        res = mul(res, a);
      }
      a = mul(a, a);
      b >>= 1;
    }
    return res;
  }
  long long reverse(long long a) { return bin_pow(a, mod - 2); }

 public:
  vector<int> operator()(const vector<int>& a, int n, bool invert) {
    assert(mod == ::mod);
    int root_1 = reverse(root);
    int pow2 = 1;
    while (pow2 < n) {
      pow2 <<= 1;
    }
    n = pow2;
    vector<int> res(n, 0);
    std::copy(a.begin(), a.end(), res.begin());
    for (int i = 1, j = 0; i < n; ++i) {
      int bit = n >> 1;
      for (; j >= bit; bit >>= 1) j -= bit;
      j += bit;
      if (i < j) swap(res[i], res[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
      int wlen = invert ? root_1 : root;
      for (int i = len; i < rootPw; i <<= 1)
        wlen = int(wlen * 1ll * wlen % mod);
      for (int i = 0; i < n; i += len) {
        int w = 1;
        for (int j = 0; j < len / 2; ++j) {
          int u = res[i + j], v = int(res[i + j + len / 2] * 1ll * w % mod);
          res[i + j] = u + v < mod ? u + v : u + v - mod;
          res[i + j + len / 2] = u - v >= 0 ? u - v : u - v + mod;
          w = int(w * 1ll * wlen % mod);
        }
      }
    }
    if (invert) {
      int nrev = reverse(n);
      for (int i = 0; i < n; ++i) res[i] = int(res[i] * 1ll * nrev % mod);
    }
    return res;
  }
};
FFT<998244353, 15311432, 1 << 23> fft;
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> c(10);
  for (int i = 0; i < k; i++) {
    int d;
    cin >> d;
    c[d] = 1;
  }
  auto res = fft(c, 5 * n, false);
  for (int i = 0; i < res.size(); i++) {
    res[i] = bin_pow(res[i], n / 2);
  }
  auto res2 = fft(res, 5 * n, true);
  long long sum = 0;
  for (int i = 0; i < res2.size(); i++) {
    sum += ((((long long)res2[i]) * ((long long)res2[i])) % mod);
    sum %= mod;
  }
  cout << sum;
}
int main(int argc, char** argv) {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(20) << fixed;
  solve();
  return 0;
}

### Prompt

Please provide a cpp coded solution 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 double eps = 1e-8;
const long long INF64 = 1e18;
const double INF = 1e9 + 63;
const long long mod = 998244353;
const int maxn = 3e3 + 79;
const long long sigma = 27;
const double pi = acos(-1);
long long bin_pow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      res %= mod;
    }
    a *= a;
    a %= mod;
    b >>= 1;
  }
  return res;
}
template <int mod, int root, int rootPw>
struct FFT {
 private:
  long long mul(long long a, long long b) { return (a * b) % mod; }
  long long bin_pow(long long a, long long b) {
    long long res = 1;
    while (b) {
      if (b & 1) {
        res = mul(res, a);
      }
      a = mul(a, a);
      b >>= 1;
    }
    return res;
  }
  long long reverse(long long a) { return bin_pow(a, mod - 2); }

 public:
  vector<int> operator()(const vector<int>& a, int n, bool invert) {
    assert(mod == ::mod);
    int root_1 = reverse(root);
    int pow2 = 1;
    while (pow2 < n) {
      pow2 <<= 1;
    }
    n = pow2;
    vector<int> res(n, 0);
    std::copy(a.begin(), a.end(), res.begin());
    for (int i = 1, j = 0; i < n; ++i) {
      int bit = n >> 1;
      for (; j >= bit; bit >>= 1) j -= bit;
      j += bit;
      if (i < j) swap(res[i], res[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
      int wlen = invert ? root_1 : root;
      for (int i = len; i < rootPw; i <<= 1)
        wlen = int(wlen * 1ll * wlen % mod);
      for (int i = 0; i < n; i += len) {
        int w = 1;
        for (int j = 0; j < len / 2; ++j) {
          int u = res[i + j], v = int(res[i + j + len / 2] * 1ll * w % mod);
          res[i + j] = u + v < mod ? u + v : u + v - mod;
          res[i + j + len / 2] = u - v >= 0 ? u - v : u - v + mod;
          w = int(w * 1ll * wlen % mod);
        }
      }
    }
    if (invert) {
      int nrev = reverse(n);
      for (int i = 0; i < n; ++i) res[i] = int(res[i] * 1ll * nrev % mod);
    }
    return res;
  }
};
FFT<998244353, 15311432, 1 << 23> fft;
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> c(10);
  for (int i = 0; i < k; i++) {
    int d;
    cin >> d;
    c[d] = 1;
  }
  auto res = fft(c, 5 * n, false);
  for (int i = 0; i < res.size(); i++) {
    res[i] = bin_pow(res[i], n / 2);
  }
  auto res2 = fft(res, 5 * n, true);
  long long sum = 0;
  for (int i = 0; i < res2.size(); i++) {
    sum += ((((long long)res2[i]) * ((long long)res2[i])) % mod);
    sum %= mod;
  }
  cout << sum;
}
int main(int argc, char** argv) {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(20) << fixed;
  solve();
  return 0;
}

```