#include <bits/stdc++.h>
using namespace std;
const int maxm = 4e6 + 10;
const int mod = 998244353;
inline int add(int a, int b) { return (a + b) % mod; }
inline long long mul(long long a, long long b) { return a * b % mod; }
struct NTT {
  long long qpow(long long x, long long n) {
    long long ans = 1;
    while (n) {
      if (n & 1) ans = ::mul(ans, x);
      x = ::mul(x, x);
      n >>= 1;
    }
    return ans;
  }
  long long getinv(long long x) {
    return x == 1 ? x : (::mul(getinv(mod % x), (mod - mod / x)));
  }
  int t[maxm * 2];
  void ntt(vector<int>& a, int n, int op) {
    for (int i = 0; i < n; i++) {
      int ind = 0, base = n >> 1;
      for (int j = 0; base; j++) {
        if (i & (1 << j)) ind += base;
        base >>= 1;
      }
      t[ind] = a[i];
    }
    for (int i = 0; i < n; i++) a[i] = t[i];
    for (int i = 1; i < n; i <<= 1) {
      long long gn, g = 1;
      if (op == 1)
        gn = qpow(3, (mod - 1) / i / 2);
      else
        gn = qpow(3, (mod - 1) / i / 2 * (i * 2 - 1));
      for (int j = 0; j < n; j += (i << 1)) {
        g = 1;
        for (int k = j; k < i + j; k++) {
          long long u = a[k], v = a[k + i];
          a[k] = add(u, ::mul(g, v));
          a[k + i] = add(u, mod - ::mul(g, v));
          g = ::mul(g, gn);
        }
      }
    }
    if (op == -1) {
      long long t = getinv(n);
      for (int i = 0; i < n; i++) {
        a[i] = ::mul(a[i], t);
      }
    }
  }
  void mul(vector<int>& a, vector<int>& b) {
    int n = 1;
    while (n < a.size() + b.size() - 1) n <<= 1;
    a.resize(n), b.resize(n);
    ntt(a, n, 1);
    ntt(b, n, 1);
    for (int i = 0; i < n; i++) a[i] = ::mul(a[i], b[i]);
    ntt(a, n, -1);
    while (a.size() > 1 && a.back() == 0) a.pop_back();
  }
} cal;
int n, k;
void show(vector<int> a) {
  for (int i : a) {
    cout << i << ' ';
  }
  cout << endl;
}
bool flag[15];
vector<int> a, b;
int main() {
  scanf("%d%d", &n, &k);
  if (k == 1) {
    puts("1");
    return 0;
  }
  for (int i = 0, nouse; i < k; i++) {
    scanf("%d", &nouse);
    flag[nouse] = true;
  }
  for (int i = 0; i < 10; i++) {
    if (flag[i])
      b.push_back(1);
    else
      b.push_back(0);
  }
  a.push_back(1);
  n >>= 1;
  while (n) {
    vector<int> c = b;
    if (n & 1) cal.mul(a, c);
    c = b;
    cal.mul(b, c);
    n >>= 1;
  }
  int ans = 0;
  for (int i : a) {
    ans = add(ans, mul(i, i));
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
const int maxm = 4e6 + 10;
const int mod = 998244353;
inline int add(int a, int b) { return (a + b) % mod; }
inline long long mul(long long a, long long b) { return a * b % mod; }
struct NTT {
  long long qpow(long long x, long long n) {
    long long ans = 1;
    while (n) {
      if (n & 1) ans = ::mul(ans, x);
      x = ::mul(x, x);
      n >>= 1;
    }
    return ans;
  }
  long long getinv(long long x) {
    return x == 1 ? x : (::mul(getinv(mod % x), (mod - mod / x)));
  }
  int t[maxm * 2];
  void ntt(vector<int>& a, int n, int op) {
    for (int i = 0; i < n; i++) {
      int ind = 0, base = n >> 1;
      for (int j = 0; base; j++) {
        if (i & (1 << j)) ind += base;
        base >>= 1;
      }
      t[ind] = a[i];
    }
    for (int i = 0; i < n; i++) a[i] = t[i];
    for (int i = 1; i < n; i <<= 1) {
      long long gn, g = 1;
      if (op == 1)
        gn = qpow(3, (mod - 1) / i / 2);
      else
        gn = qpow(3, (mod - 1) / i / 2 * (i * 2 - 1));
      for (int j = 0; j < n; j += (i << 1)) {
        g = 1;
        for (int k = j; k < i + j; k++) {
          long long u = a[k], v = a[k + i];
          a[k] = add(u, ::mul(g, v));
          a[k + i] = add(u, mod - ::mul(g, v));
          g = ::mul(g, gn);
        }
      }
    }
    if (op == -1) {
      long long t = getinv(n);
      for (int i = 0; i < n; i++) {
        a[i] = ::mul(a[i], t);
      }
    }
  }
  void mul(vector<int>& a, vector<int>& b) {
    int n = 1;
    while (n < a.size() + b.size() - 1) n <<= 1;
    a.resize(n), b.resize(n);
    ntt(a, n, 1);
    ntt(b, n, 1);
    for (int i = 0; i < n; i++) a[i] = ::mul(a[i], b[i]);
    ntt(a, n, -1);
    while (a.size() > 1 && a.back() == 0) a.pop_back();
  }
} cal;
int n, k;
void show(vector<int> a) {
  for (int i : a) {
    cout << i << ' ';
  }
  cout << endl;
}
bool flag[15];
vector<int> a, b;
int main() {
  scanf("%d%d", &n, &k);
  if (k == 1) {
    puts("1");
    return 0;
  }
  for (int i = 0, nouse; i < k; i++) {
    scanf("%d", &nouse);
    flag[nouse] = true;
  }
  for (int i = 0; i < 10; i++) {
    if (flag[i])
      b.push_back(1);
    else
      b.push_back(0);
  }
  a.push_back(1);
  n >>= 1;
  while (n) {
    vector<int> c = b;
    if (n & 1) cal.mul(a, c);
    c = b;
    cal.mul(b, c);
    n >>= 1;
  }
  int ans = 0;
  for (int i : a) {
    ans = add(ans, mul(i, i));
  }
  printf("%d\n", ans);
  return 0;
}

```