#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int maxn = 2e5 + 10;
inline long long qpow(long long x, long long n) {
  long long ret = 1ll;
  while (n) {
    if (n % 2) ret = ret * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return ret;
}
vector<bool> D;
vector<vector<long long>> poly;
int N, K;
void change(vector<long long>& y, int len) {
  int i, j, k;
  for (i = 1, j = len / 2; i < len - 1; i++) {
    if (i < j) swap(y[i], y[j]);
    k = len / 2;
    while (j >= k) {
      j = j - k;
      k = k / 2;
    }
    if (j < k) j += k;
  }
}
void NTT(vector<long long>& P, int op) {
  int len = P.size(), i, j, k;
  change(P, len);
  for (i = 1; i < len; i <<= 1) {
    long long gn = qpow(3ll, (mod - 1) / (i << 1));
    if (op == -1) gn = qpow(gn, mod - 2);
    for (j = 0; j < len; j += (i << 1)) {
      long long g = 1;
      for (k = 0; k < i; ++k, g = g * gn % mod) {
        long long x = P[j + k], y = g * P[j + k + i] % mod;
        P[j + k] = (x + y) % mod;
        P[j + k + i] = (x - y + mod) % mod;
      }
    }
  }
  if (op == -1) {
    long long inv = qpow(len, mod - 2);
    for (i = 0; i < len; ++i) P[i] = P[i] * inv % mod;
  }
}
vector<long long> multiply(vector<long long> aa, vector<long long> bb) {
  int n = aa.size(), m = bb.size(), len = 1, i;
  while (len < n + m) len <<= 1;
  vector<long long> a(len), b(len);
  for (i = 0; i < n; ++i) a[i] = aa[i];
  for (i = 0; i < m; ++i) b[i] = bb[i];
  NTT(a, 1);
  NTT(b, 1);
  vector<long long> c(len);
  for (i = 0; i < len; ++i) c[i] = a[i] * b[i] % mod;
  NTT(c, -1);
  while (!c.empty() && c.back() == 0) c.pop_back();
  return c;
}
vector<long long> solve(vector<long long>& v, int n) {
  vector<long long> ret = {1};
  while (n) {
    if (n & 1) ret = multiply(ret, v);
    v = multiply(v, v);
    n >>= 1;
  }
  return ret;
}
int main() {
  D = vector<bool>(10);
  poly = vector<vector<long long>>();
  int i, j;
  scanf("%d %d", &N, &K);
  for (i = 1; i <= K; ++i) {
    int x;
    scanf("%d", &x);
    D[x] = 1;
  }
  vector<long long> v;
  for (j = 0; j < 10; ++j) {
    v.push_back(D[j]);
  }
  poly.push_back(v);
  vector<long long> first_half = solve(v, N / 2);
  long long ans = 0;
  for (long long x : first_half) {
    ans += x * x % mod;
    ans %= mod;
  }
  printf("%lld\n", (ans + mod) % mod);
}

### 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 long long mod = 998244353;
const int maxn = 2e5 + 10;
inline long long qpow(long long x, long long n) {
  long long ret = 1ll;
  while (n) {
    if (n % 2) ret = ret * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return ret;
}
vector<bool> D;
vector<vector<long long>> poly;
int N, K;
void change(vector<long long>& y, int len) {
  int i, j, k;
  for (i = 1, j = len / 2; i < len - 1; i++) {
    if (i < j) swap(y[i], y[j]);
    k = len / 2;
    while (j >= k) {
      j = j - k;
      k = k / 2;
    }
    if (j < k) j += k;
  }
}
void NTT(vector<long long>& P, int op) {
  int len = P.size(), i, j, k;
  change(P, len);
  for (i = 1; i < len; i <<= 1) {
    long long gn = qpow(3ll, (mod - 1) / (i << 1));
    if (op == -1) gn = qpow(gn, mod - 2);
    for (j = 0; j < len; j += (i << 1)) {
      long long g = 1;
      for (k = 0; k < i; ++k, g = g * gn % mod) {
        long long x = P[j + k], y = g * P[j + k + i] % mod;
        P[j + k] = (x + y) % mod;
        P[j + k + i] = (x - y + mod) % mod;
      }
    }
  }
  if (op == -1) {
    long long inv = qpow(len, mod - 2);
    for (i = 0; i < len; ++i) P[i] = P[i] * inv % mod;
  }
}
vector<long long> multiply(vector<long long> aa, vector<long long> bb) {
  int n = aa.size(), m = bb.size(), len = 1, i;
  while (len < n + m) len <<= 1;
  vector<long long> a(len), b(len);
  for (i = 0; i < n; ++i) a[i] = aa[i];
  for (i = 0; i < m; ++i) b[i] = bb[i];
  NTT(a, 1);
  NTT(b, 1);
  vector<long long> c(len);
  for (i = 0; i < len; ++i) c[i] = a[i] * b[i] % mod;
  NTT(c, -1);
  while (!c.empty() && c.back() == 0) c.pop_back();
  return c;
}
vector<long long> solve(vector<long long>& v, int n) {
  vector<long long> ret = {1};
  while (n) {
    if (n & 1) ret = multiply(ret, v);
    v = multiply(v, v);
    n >>= 1;
  }
  return ret;
}
int main() {
  D = vector<bool>(10);
  poly = vector<vector<long long>>();
  int i, j;
  scanf("%d %d", &N, &K);
  for (i = 1; i <= K; ++i) {
    int x;
    scanf("%d", &x);
    D[x] = 1;
  }
  vector<long long> v;
  for (j = 0; j < 10; ++j) {
    v.push_back(D[j]);
  }
  poly.push_back(v);
  vector<long long> first_half = solve(v, N / 2);
  long long ans = 0;
  for (long long x : first_half) {
    ans += x * x % mod;
    ans %= mod;
  }
  printf("%lld\n", (ans + mod) % mod);
}

```