#include <bits/stdc++.h>
const int N = 5.3e6 + 635, P = 998244353, G = 3;
int pw(int x, int y) {
  int r = 1;
  for (; y; y >>= 1, x = (unsigned long long)x * x % P)
    if (y & 1) r = (unsigned long long)r * x % P;
  return r;
}
unsigned long long tmp[N];
struct poly {
  std::vector<int> v;
  poly() {}
  poly(const poly &rhs) : v(rhs.v) {}
  inline void resize(size_t n) { v.resize(n); }
  inline size_t size() { return v.size(); }
  inline void shrink() {
    while (!v.empty() && !v.back()) v.pop_back();
  }
  inline int &operator[](int i) { return v[i]; }
  inline static int len(int n) { return 1 << (32 - __builtin_clz(n - 1)); }
  void dft(int n) {
    resize(n);
    if (n <= 1) return;
    for (int i = 0, ri = 0; i < n; i++) {
      tmp[i] = v[ri];
      for (int k = n / 2; (ri ^= k) < k;) k >>= 1;
    }
    for (int i = 1; i < n; i <<= 1) {
      int wn = pw(G, (P - 1) / (i << 1));
      for (int j = 0; j < n; j += i << 1) {
        unsigned long long *a = tmp + j, *b = tmp + j + i;
        for (int k = 0, w = 1; k < i; k++, w = (unsigned long long)w * wn % P) {
          int y = b[k] * w % P;
          b[k] = a[k] + P - y, a[k] += y;
        }
      }
    }
    for (int i = 0; i < n; i++) v[i] = tmp[i] % P;
  }
  void idft(int n) {
    dft(n);
    std::reverse(v.begin() + 1, v.end());
    int inv = P - (P - 1) / n;
    for (int &i : v) i = (unsigned long long)i * inv % P;
  }
  void mul(poly rhs) {
    int n = len(size() + rhs.size() - 1);
    dft(n), rhs.dft(n);
    for (int i = 0; i < n; i++) v[i] = (unsigned long long)v[i] * rhs[i] % P;
    idft(n), shrink();
  }
} f, g;
std::vector<int> digit;
int n, k, x;
unsigned long long ans;
int main() {
  scanf("%d%d", &n, &k);
  f.resize(10);
  while (k--) scanf("%d", &x), f[x] = 1;
  g.resize(1), g[0] = 1;
  for (int i = n / 2; i; i >>= 1, f.mul(f))
    if (i & 1) g.mul(f);
  for (int i : g.v) ans += (unsigned long long)i * i % P;
  printf("%llu", ans % P);
}

### Prompt

Your challenge is to write 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>
const int N = 5.3e6 + 635, P = 998244353, G = 3;
int pw(int x, int y) {
  int r = 1;
  for (; y; y >>= 1, x = (unsigned long long)x * x % P)
    if (y & 1) r = (unsigned long long)r * x % P;
  return r;
}
unsigned long long tmp[N];
struct poly {
  std::vector<int> v;
  poly() {}
  poly(const poly &rhs) : v(rhs.v) {}
  inline void resize(size_t n) { v.resize(n); }
  inline size_t size() { return v.size(); }
  inline void shrink() {
    while (!v.empty() && !v.back()) v.pop_back();
  }
  inline int &operator[](int i) { return v[i]; }
  inline static int len(int n) { return 1 << (32 - __builtin_clz(n - 1)); }
  void dft(int n) {
    resize(n);
    if (n <= 1) return;
    for (int i = 0, ri = 0; i < n; i++) {
      tmp[i] = v[ri];
      for (int k = n / 2; (ri ^= k) < k;) k >>= 1;
    }
    for (int i = 1; i < n; i <<= 1) {
      int wn = pw(G, (P - 1) / (i << 1));
      for (int j = 0; j < n; j += i << 1) {
        unsigned long long *a = tmp + j, *b = tmp + j + i;
        for (int k = 0, w = 1; k < i; k++, w = (unsigned long long)w * wn % P) {
          int y = b[k] * w % P;
          b[k] = a[k] + P - y, a[k] += y;
        }
      }
    }
    for (int i = 0; i < n; i++) v[i] = tmp[i] % P;
  }
  void idft(int n) {
    dft(n);
    std::reverse(v.begin() + 1, v.end());
    int inv = P - (P - 1) / n;
    for (int &i : v) i = (unsigned long long)i * inv % P;
  }
  void mul(poly rhs) {
    int n = len(size() + rhs.size() - 1);
    dft(n), rhs.dft(n);
    for (int i = 0; i < n; i++) v[i] = (unsigned long long)v[i] * rhs[i] % P;
    idft(n), shrink();
  }
} f, g;
std::vector<int> digit;
int n, k, x;
unsigned long long ans;
int main() {
  scanf("%d%d", &n, &k);
  f.resize(10);
  while (k--) scanf("%d", &x), f[x] = 1;
  g.resize(1), g[0] = 1;
  for (int i = n / 2; i; i >>= 1, f.mul(f))
    if (i & 1) g.mul(f);
  for (int i : g.v) ans += (unsigned long long)i * i % P;
  printf("%llu", ans % P);
}

```