#include <bits/stdc++.h>
const long long inf = (long long)1e18 + 7;
const long long Mod = (long long)998244353;
using namespace std;
long long modexpo(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) {
      ret = (ret * a) % Mod;
    }
    a = (a * a) % Mod;
    b >>= 1;
  }
  return ret;
}
vector<long long> fft(vector<long long> v, bool rev = false) {
  long long n = v.size(), i, j, m;
  for (i = 0, j = 1; j < n - 1; j++) {
    for (long long k = n >> 1; k > (i ^= k); k >>= 1)
      ;
    if (i > j) swap(v[i], v[j]);
  }
  for (long long m = 2; m <= n; m *= 2) {
    long long wn = modexpo(5, (Mod - 1) / m);
    if (rev) wn = modexpo(wn, Mod - 2);
    for (i = 0; i < n; i += m) {
      long long w = 1;
      for (long long j1 = i, j2 = i + m / 2; j2 < i + m; j1++, j2++) {
        long long t1 = v[j1], t2 = w * v[j2] % Mod;
        v[j1] = t1 + t2;
        v[j2] = t1 + Mod - t2;
        while (v[j1] >= Mod) v[j1] -= Mod;
        while (v[j2] >= Mod) v[j2] -= Mod;
        w = (w * wn) % Mod;
      }
    }
  }
  if (rev) {
    long long invn = modexpo(n, Mod - 2);
    for (i = 0; i < n; i++) v[i] = (v[i] * invn) % Mod;
  }
  return v;
}
vector<long long> MultPoly(vector<long long> P, vector<long long> Q,
                           bool isequal = false) {
  bool resize = true;
  if (resize) {
    long long maxind = 0, pi = 0, qi = 0, i;
    long long s = 2;
    for (long long i = 0; i < P.size(); i++)
      if (P[i]) pi = i;
    for (long long i = 0; i < Q.size(); i++)
      if (Q[i]) qi = i;
    maxind = pi + qi + 1;
    while (s * 2 < maxind) s *= 2;
    P.resize(s * 2);
    Q.resize(s * 2);
  }
  P = fft(P);
  if (isequal == false)
    Q = fft(Q);
  else
    Q = P;
  for (long long i = 0; i < P.size(); i++) P[i] = (P[i] * Q[i]) % Mod;
  return fft(P, true);
}
vector<long long> modexpov(vector<long long> v, long long b) {
  vector<long long> ret(1, 1);
  while (b) {
    if (b & 1) {
      ret = MultPoly(ret, v);
    }
    v = MultPoly(v, v, true);
    b >>= 1;
  }
  return ret;
}
long long freq[10];
int main() {
  long long i, n, x, k, ans = 0;
  cin >> n >> k;
  long long arr[n];
  for (i = 0; i < k; i++) {
    cin >> x;
    freq[x]++;
  }
  vector<long long> D, v;
  for (i = 0; i < 10; i++) {
    v.push_back(freq[i]);
  }
  D = modexpov(v, n / 2);
  for (i = 0; i < D.size(); i++) {
    ans = (ans + (D[i] * D[i]) % Mod) % Mod;
  }
  cout << ans << endl;
  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>
const long long inf = (long long)1e18 + 7;
const long long Mod = (long long)998244353;
using namespace std;
long long modexpo(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) {
      ret = (ret * a) % Mod;
    }
    a = (a * a) % Mod;
    b >>= 1;
  }
  return ret;
}
vector<long long> fft(vector<long long> v, bool rev = false) {
  long long n = v.size(), i, j, m;
  for (i = 0, j = 1; j < n - 1; j++) {
    for (long long k = n >> 1; k > (i ^= k); k >>= 1)
      ;
    if (i > j) swap(v[i], v[j]);
  }
  for (long long m = 2; m <= n; m *= 2) {
    long long wn = modexpo(5, (Mod - 1) / m);
    if (rev) wn = modexpo(wn, Mod - 2);
    for (i = 0; i < n; i += m) {
      long long w = 1;
      for (long long j1 = i, j2 = i + m / 2; j2 < i + m; j1++, j2++) {
        long long t1 = v[j1], t2 = w * v[j2] % Mod;
        v[j1] = t1 + t2;
        v[j2] = t1 + Mod - t2;
        while (v[j1] >= Mod) v[j1] -= Mod;
        while (v[j2] >= Mod) v[j2] -= Mod;
        w = (w * wn) % Mod;
      }
    }
  }
  if (rev) {
    long long invn = modexpo(n, Mod - 2);
    for (i = 0; i < n; i++) v[i] = (v[i] * invn) % Mod;
  }
  return v;
}
vector<long long> MultPoly(vector<long long> P, vector<long long> Q,
                           bool isequal = false) {
  bool resize = true;
  if (resize) {
    long long maxind = 0, pi = 0, qi = 0, i;
    long long s = 2;
    for (long long i = 0; i < P.size(); i++)
      if (P[i]) pi = i;
    for (long long i = 0; i < Q.size(); i++)
      if (Q[i]) qi = i;
    maxind = pi + qi + 1;
    while (s * 2 < maxind) s *= 2;
    P.resize(s * 2);
    Q.resize(s * 2);
  }
  P = fft(P);
  if (isequal == false)
    Q = fft(Q);
  else
    Q = P;
  for (long long i = 0; i < P.size(); i++) P[i] = (P[i] * Q[i]) % Mod;
  return fft(P, true);
}
vector<long long> modexpov(vector<long long> v, long long b) {
  vector<long long> ret(1, 1);
  while (b) {
    if (b & 1) {
      ret = MultPoly(ret, v);
    }
    v = MultPoly(v, v, true);
    b >>= 1;
  }
  return ret;
}
long long freq[10];
int main() {
  long long i, n, x, k, ans = 0;
  cin >> n >> k;
  long long arr[n];
  for (i = 0; i < k; i++) {
    cin >> x;
    freq[x]++;
  }
  vector<long long> D, v;
  for (i = 0; i < 10; i++) {
    v.push_back(freq[i]);
  }
  D = modexpov(v, n / 2);
  for (i = 0; i < D.size(); i++) {
    ans = (ans + (D[i] * D[i]) % Mod) % Mod;
  }
  cout << ans << endl;
  return 0;
}

```