#include <bits/stdc++.h>
using namespace std;
namespace fft {
int len, last = -1, step = 0, rev[1 << 20];
long long C[1 << 20], D[1 << 20], P[1 << 20], Q[1 << 20];
struct complx {
  long double real, img;
  inline complx() { real = img = 0.0; }
  inline complx conjugate() { return complx(real, -img); }
  inline complx(long double x) { real = x, img = 0.0; }
  inline complx(long double x, long double y) { real = x, img = y; }
  inline complx operator+(complx other) {
    return complx(real + other.real, img + other.img);
  }
  inline complx operator-(complx other) {
    return complx(real - other.real, img - other.img);
  }
  inline complx operator*(complx other) {
    return complx((real * other.real) - (img * other.img),
                  (real * other.img) + (img * other.real));
  }
} u[1 << 20], v[1 << 20], f[1 << 20], g[1 << 20], dp[1 << 20], inv[1 << 20];
void build(int& a, long long* A, int& b, long long* B) {
  while (a > 1 && A[a - 1] == 0) a--;
  while (b > 1 && B[b - 1] == 0) b--;
  len = 1 << (32 - __builtin_clz(a + b) - (__builtin_popcount(a + b) == 1));
  for (int i = a; i < len; i++) A[i] = 0;
  for (int i = b; i < len; i++) B[i] = 0;
  if (!step++) {
    dp[1] = inv[1] = complx(1);
    for (int i = 1; (1 << i) < 1 << 20; i++) {
      double theta = (2.0 * acos(0.0)) / (1 << i);
      complx mul = complx(cos(theta), sin(theta));
      complx inv_mul = complx(cos(-theta), sin(-theta));
      int lim = 1 << i;
      for (int j = lim >> 1; j < lim; j++) {
        dp[2 * j] = dp[j], inv[2 * j] = inv[j];
        inv[2 * j + 1] = inv[j] * inv_mul;
        dp[2 * j + 1] = dp[j] * mul;
      }
    }
  }
  if (last != len) {
    last = len;
    int bit = (32 - __builtin_clz(len) - (__builtin_popcount(len) == 1));
    for (int i = 0; i < len; i++)
      rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (bit - 1));
  }
}
void transform(complx* in, complx* out, complx* ar) {
  for (int i = 0; i < len; i++) out[i] = in[rev[i]];
  for (int k = 1; k < len; k <<= 1) {
    for (int i = 0; i < len; i += (k << 1)) {
      for (int j = 0; j < k; j++) {
        complx z = out[i + j + k] * ar[j + k];
        out[i + j + k] = out[i + j] - z;
        out[i + j] = out[i + j] + z;
      }
    }
  }
}
void transform_unrolled(complx* in, complx* out, complx* ar) {
  for (int i = 0; i < len; i++) out[i] = in[rev[i]];
  for (int k = 1; k < len; k <<= 1) {
    for (int i = 0; i < len; i += (k << 1)) {
      complx z, *a = out + i, *b = out + i + k, *c = ar + k;
      if (k == 1) {
        z = (*b) * (*c);
        *b = *a - z, *a = *a + z;
      }
      for (int j = 0; j < k && k > 1; j += 2, a++, b++, c++) {
        z = (*b) * (*c);
        *b = *a - z, *a = *a + z;
        a++, b++, c++;
        z = (*b) * (*c);
        *b = *a - z, *a = *a + z;
      }
    }
  }
}
bool equals(int a, long long* A, int b, long long* B) {
  if (a != b) return false;
  for (a = 0; a < b && A[a] == B[a]; a++) {
  }
  return (a == b);
}
int square(int a, long long* A) {
  build(a, A, a, A);
  for (int i = 0; i < len; i++) u[i] = complx(A[i], 0);
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) u[i] = f[i] * f[i];
  transform_unrolled(u, f, inv);
  for (int i = 0; i < len; i++) A[i] = (f[i].real / (long double)len) + 0.5;
  return a + a - 1;
}
int multiply(int a, long long* A, int b, long long* B) {
  if (equals(a, A, b, B)) return square(a, A);
  build(a, A, b, B);
  for (int i = 0; i < len; i++) u[i] = complx(A[i], B[i]);
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) {
    int j = (len - 1) & (len - i);
    u[i] = (f[j] * f[j] - f[i].conjugate() * f[i].conjugate()) *
           complx(0, -0.25 / len);
  }
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) A[i] = f[i].real + 0.5;
  return a + b - 1;
}
int mod_multiply(int a, long long* A, int b, long long* B, int mod) {
  build(a, A, b, B);
  int flag = equals(a, A, b, B);
  for (int i = 0; i < len; i++) A[i] %= mod, B[i] %= mod;
  for (int i = 0; i < len; i++) u[i] = complx(A[i] & 32767, A[i] >> 15);
  for (int i = 0; i < len; i++) v[i] = complx(B[i] & 32767, B[i] >> 15);
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) g[i] = f[i];
  if (!flag) transform_unrolled(v, g, dp);
  for (int i = 0; i < len; i++) {
    int j = (len - 1) & (len - i);
    complx c1 = f[j].conjugate(), c2 = g[j].conjugate();
    complx a1 = (f[i] + c1) * complx(0.5, 0);
    complx a2 = (f[i] - c1) * complx(0, -0.5);
    complx b1 = (g[i] + c2) * complx(0.5 / len, 0);
    complx b2 = (g[i] - c2) * complx(0, -0.5 / len);
    v[j] = a1 * b2 + a2 * b1;
    u[j] = a1 * b1 + a2 * b2 * complx(0, 1);
  }
  transform_unrolled(u, f, dp);
  transform_unrolled(v, g, dp);
  long long x, y, z;
  for (int i = 0; i < len; i++) {
    x = f[i].real + 0.5, y = g[i].real + 0.5, z = f[i].img + 0.5;
    A[i] = (x + ((y % mod) << 15) + ((z % mod) << 30)) % mod;
  }
  return a + b - 1;
}
int long_multiply(int a, long long* A, int b, long long* B) {
  int mod1 = 1.5e9;
  int mod2 = mod1 + 1;
  for (int i = 0; i < a; i++) C[i] = A[i];
  for (int i = 0; i < b; i++) D[i] = B[i];
  mod_multiply(a, A, b, B, mod1);
  mod_multiply(a, C, b, D, mod2);
  for (int i = 0; i < len; i++) {
    A[i] =
        A[i] + (C[i] - A[i] + (long long)mod2) * (long long)mod1 % mod2 * mod1;
  }
  return a + b - 1;
}
int build_convolution(int n, long long* A, long long* B) {
  int i, m, d = 0;
  for (i = 0; i < n; i++) Q[i] = Q[i + n] = B[i];
  for (i = 0; i < n; i++) P[i] = A[i], P[i + n] = 0;
  n *= 2, m = 1 << (32 - __builtin_clz(n) - (__builtin_popcount(n) == 1));
  for (i = n; i < m; i++) P[i] = Q[i] = 0;
  return n;
}
void convolution(int n, long long* A, long long* B) {
  int len = build_convolution(n, A, B);
  multiply(len, P, len, Q);
  for (int i = 0; i < n; i++) A[i] = P[i + n];
}
void mod_convolution(int n, long long* A, long long* B, int mod) {
  int len = build_convolution(n, A, B);
  mod_multiply(len, P, len, Q, mod);
  for (int i = 0; i < n; i++) A[i] = P[i + n];
}
void long_convolution(int n, long long* A, long long* B) {
  int len = build_convolution(n, A, B);
  long_multiply(len, P, len, Q);
  for (int i = 0; i < n; i++) A[i] = P[i + n];
}
vector<int> hamming_distance(const char* str, const char* pattern) {
  int n = strlen(str), m = strlen(pattern);
  for (int i = 0; i < n; i++) P[i] = Q[i] = 0;
  for (int i = 0; i < n; i++) P[i] = str[i] == '1' ? 1 : -1;
  for (int i = 0, j = m - 1; j >= 0; i++, j--)
    Q[i] = pattern[j] == '1' ? 1 : -1;
  vector<int> res;
  fft::multiply(n, P, m, Q);
  for (int i = 0; (i + m) <= n; i++) {
    res.push_back(m - ((P[i + m - 1] + m) >> 1));
  }
  return res;
}
}  // namespace fft
int n, m;
long long A[1 << 20], B[1 << 20];
int bigmod(int p) {
  if (p == 1) return 10;
  int x = bigmod(p / 2);
  x = fft::mod_multiply(x, A, x, A, 998244353);
  if (p & 1) {
    x = fft::mod_multiply(x, A, 10, B, 998244353);
  }
  return x;
}
int main() {
  scanf("%d", &n);
  scanf("%d", &m);
  int x;
  for (int i = 0; i < m; i++) {
    scanf("%d", &x);
    A[x] = 1;
    B[x] = 1;
  }
  x = bigmod(n / 2);
  long long ans = 0;
  for (int i = 0; i < x; i++) {
    if (A[i]) {
      ans += (A[i] * A[i]);
      ans %= 998244353;
    }
  }
  cout << ans << endl;
}

### 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>
using namespace std;
namespace fft {
int len, last = -1, step = 0, rev[1 << 20];
long long C[1 << 20], D[1 << 20], P[1 << 20], Q[1 << 20];
struct complx {
  long double real, img;
  inline complx() { real = img = 0.0; }
  inline complx conjugate() { return complx(real, -img); }
  inline complx(long double x) { real = x, img = 0.0; }
  inline complx(long double x, long double y) { real = x, img = y; }
  inline complx operator+(complx other) {
    return complx(real + other.real, img + other.img);
  }
  inline complx operator-(complx other) {
    return complx(real - other.real, img - other.img);
  }
  inline complx operator*(complx other) {
    return complx((real * other.real) - (img * other.img),
                  (real * other.img) + (img * other.real));
  }
} u[1 << 20], v[1 << 20], f[1 << 20], g[1 << 20], dp[1 << 20], inv[1 << 20];
void build(int& a, long long* A, int& b, long long* B) {
  while (a > 1 && A[a - 1] == 0) a--;
  while (b > 1 && B[b - 1] == 0) b--;
  len = 1 << (32 - __builtin_clz(a + b) - (__builtin_popcount(a + b) == 1));
  for (int i = a; i < len; i++) A[i] = 0;
  for (int i = b; i < len; i++) B[i] = 0;
  if (!step++) {
    dp[1] = inv[1] = complx(1);
    for (int i = 1; (1 << i) < 1 << 20; i++) {
      double theta = (2.0 * acos(0.0)) / (1 << i);
      complx mul = complx(cos(theta), sin(theta));
      complx inv_mul = complx(cos(-theta), sin(-theta));
      int lim = 1 << i;
      for (int j = lim >> 1; j < lim; j++) {
        dp[2 * j] = dp[j], inv[2 * j] = inv[j];
        inv[2 * j + 1] = inv[j] * inv_mul;
        dp[2 * j + 1] = dp[j] * mul;
      }
    }
  }
  if (last != len) {
    last = len;
    int bit = (32 - __builtin_clz(len) - (__builtin_popcount(len) == 1));
    for (int i = 0; i < len; i++)
      rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (bit - 1));
  }
}
void transform(complx* in, complx* out, complx* ar) {
  for (int i = 0; i < len; i++) out[i] = in[rev[i]];
  for (int k = 1; k < len; k <<= 1) {
    for (int i = 0; i < len; i += (k << 1)) {
      for (int j = 0; j < k; j++) {
        complx z = out[i + j + k] * ar[j + k];
        out[i + j + k] = out[i + j] - z;
        out[i + j] = out[i + j] + z;
      }
    }
  }
}
void transform_unrolled(complx* in, complx* out, complx* ar) {
  for (int i = 0; i < len; i++) out[i] = in[rev[i]];
  for (int k = 1; k < len; k <<= 1) {
    for (int i = 0; i < len; i += (k << 1)) {
      complx z, *a = out + i, *b = out + i + k, *c = ar + k;
      if (k == 1) {
        z = (*b) * (*c);
        *b = *a - z, *a = *a + z;
      }
      for (int j = 0; j < k && k > 1; j += 2, a++, b++, c++) {
        z = (*b) * (*c);
        *b = *a - z, *a = *a + z;
        a++, b++, c++;
        z = (*b) * (*c);
        *b = *a - z, *a = *a + z;
      }
    }
  }
}
bool equals(int a, long long* A, int b, long long* B) {
  if (a != b) return false;
  for (a = 0; a < b && A[a] == B[a]; a++) {
  }
  return (a == b);
}
int square(int a, long long* A) {
  build(a, A, a, A);
  for (int i = 0; i < len; i++) u[i] = complx(A[i], 0);
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) u[i] = f[i] * f[i];
  transform_unrolled(u, f, inv);
  for (int i = 0; i < len; i++) A[i] = (f[i].real / (long double)len) + 0.5;
  return a + a - 1;
}
int multiply(int a, long long* A, int b, long long* B) {
  if (equals(a, A, b, B)) return square(a, A);
  build(a, A, b, B);
  for (int i = 0; i < len; i++) u[i] = complx(A[i], B[i]);
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) {
    int j = (len - 1) & (len - i);
    u[i] = (f[j] * f[j] - f[i].conjugate() * f[i].conjugate()) *
           complx(0, -0.25 / len);
  }
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) A[i] = f[i].real + 0.5;
  return a + b - 1;
}
int mod_multiply(int a, long long* A, int b, long long* B, int mod) {
  build(a, A, b, B);
  int flag = equals(a, A, b, B);
  for (int i = 0; i < len; i++) A[i] %= mod, B[i] %= mod;
  for (int i = 0; i < len; i++) u[i] = complx(A[i] & 32767, A[i] >> 15);
  for (int i = 0; i < len; i++) v[i] = complx(B[i] & 32767, B[i] >> 15);
  transform_unrolled(u, f, dp);
  for (int i = 0; i < len; i++) g[i] = f[i];
  if (!flag) transform_unrolled(v, g, dp);
  for (int i = 0; i < len; i++) {
    int j = (len - 1) & (len - i);
    complx c1 = f[j].conjugate(), c2 = g[j].conjugate();
    complx a1 = (f[i] + c1) * complx(0.5, 0);
    complx a2 = (f[i] - c1) * complx(0, -0.5);
    complx b1 = (g[i] + c2) * complx(0.5 / len, 0);
    complx b2 = (g[i] - c2) * complx(0, -0.5 / len);
    v[j] = a1 * b2 + a2 * b1;
    u[j] = a1 * b1 + a2 * b2 * complx(0, 1);
  }
  transform_unrolled(u, f, dp);
  transform_unrolled(v, g, dp);
  long long x, y, z;
  for (int i = 0; i < len; i++) {
    x = f[i].real + 0.5, y = g[i].real + 0.5, z = f[i].img + 0.5;
    A[i] = (x + ((y % mod) << 15) + ((z % mod) << 30)) % mod;
  }
  return a + b - 1;
}
int long_multiply(int a, long long* A, int b, long long* B) {
  int mod1 = 1.5e9;
  int mod2 = mod1 + 1;
  for (int i = 0; i < a; i++) C[i] = A[i];
  for (int i = 0; i < b; i++) D[i] = B[i];
  mod_multiply(a, A, b, B, mod1);
  mod_multiply(a, C, b, D, mod2);
  for (int i = 0; i < len; i++) {
    A[i] =
        A[i] + (C[i] - A[i] + (long long)mod2) * (long long)mod1 % mod2 * mod1;
  }
  return a + b - 1;
}
int build_convolution(int n, long long* A, long long* B) {
  int i, m, d = 0;
  for (i = 0; i < n; i++) Q[i] = Q[i + n] = B[i];
  for (i = 0; i < n; i++) P[i] = A[i], P[i + n] = 0;
  n *= 2, m = 1 << (32 - __builtin_clz(n) - (__builtin_popcount(n) == 1));
  for (i = n; i < m; i++) P[i] = Q[i] = 0;
  return n;
}
void convolution(int n, long long* A, long long* B) {
  int len = build_convolution(n, A, B);
  multiply(len, P, len, Q);
  for (int i = 0; i < n; i++) A[i] = P[i + n];
}
void mod_convolution(int n, long long* A, long long* B, int mod) {
  int len = build_convolution(n, A, B);
  mod_multiply(len, P, len, Q, mod);
  for (int i = 0; i < n; i++) A[i] = P[i + n];
}
void long_convolution(int n, long long* A, long long* B) {
  int len = build_convolution(n, A, B);
  long_multiply(len, P, len, Q);
  for (int i = 0; i < n; i++) A[i] = P[i + n];
}
vector<int> hamming_distance(const char* str, const char* pattern) {
  int n = strlen(str), m = strlen(pattern);
  for (int i = 0; i < n; i++) P[i] = Q[i] = 0;
  for (int i = 0; i < n; i++) P[i] = str[i] == '1' ? 1 : -1;
  for (int i = 0, j = m - 1; j >= 0; i++, j--)
    Q[i] = pattern[j] == '1' ? 1 : -1;
  vector<int> res;
  fft::multiply(n, P, m, Q);
  for (int i = 0; (i + m) <= n; i++) {
    res.push_back(m - ((P[i + m - 1] + m) >> 1));
  }
  return res;
}
}  // namespace fft
int n, m;
long long A[1 << 20], B[1 << 20];
int bigmod(int p) {
  if (p == 1) return 10;
  int x = bigmod(p / 2);
  x = fft::mod_multiply(x, A, x, A, 998244353);
  if (p & 1) {
    x = fft::mod_multiply(x, A, 10, B, 998244353);
  }
  return x;
}
int main() {
  scanf("%d", &n);
  scanf("%d", &m);
  int x;
  for (int i = 0; i < m; i++) {
    scanf("%d", &x);
    A[x] = 1;
    B[x] = 1;
  }
  x = bigmod(n / 2);
  long long ans = 0;
  for (int i = 0; i < x; i++) {
    if (A[i]) {
      ans += (A[i] * A[i]);
      ans %= 998244353;
    }
  }
  cout << ans << endl;
}

```