题解 | #挑选队友#

考虑每个大小为 $a_i$ 的队伍构造生成函数 $f_i(x)=(1+x)^{a_i}-1$
于是答案是 $[x^k]F(x)=\prod\limits_{i=1}^mf_i(x)$
注意到 $F(x-1)=\prod\limits_{i=1}^m(x^{a_i}-1)$
这个可以分治 $ntt$ 算出。
然后把 $F(x-1)$ 转化成 $F(x)$ 即可，就是等价于跟组合数卷积一下。
#include <bits/stdc++.h>
#define ri int
using namespace std;
typedef double db;
typedef long double ld;
typedef long long ll;
typedef vector <int> poly;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef unsigned long long ulll;
typedef unsigned int uii;
typedef string strr;
#define fi first
#define se second
#define pb push_back
#define ppp pop_back
#define rez resize
const ll Inf = 1e18;
const int rlen = 1 << 20, inf = 0x3f3f3f3f;
char buf[rlen], *ib = buf, *ob = buf;
#define gc() (((ib == ob) && (ob = (ib = buf) + fread(buf, 1, rlen, stdin)), ib == ob) ? -1 : *ib++)
inline int read() {
  static int ans, f;
  static char ch;
  ans = 0, ch = gc(), f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = gc();
  while (isdigit(ch)) ans = (ans << 3) + (ans << 1) + (ch ^ 48), ch = gc();
  return f ? ans: -ans;
}
inline ll readl() {
  static ll ans;
  static char ch;
  for (ans = 0, ch = gc(); !isdigit(ch); ch = gc());
  while (isdigit(ch)) ans = ((ans << 2) + ans << 1) + (ch ^ 48), ch = gc();
  return ans;
}
inline int Read(char *s) {
  static int top;
  static char ch;
  top = 0, ch = gc();
  while (!isalpha(ch) && !isdigit(ch)) ch = gc();
  while (isalpha(ch) || isdigit(ch)) s[++top] = ch, ch = gc();
  return top;
}
namespace modular {
  const int mod = 998244353;
  int ret;
  inline int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
  inline int dec(int a, int b) { return a < b ? a - b + mod : a - b; }
  inline int mul(int a, int b) { return (ll) a * b % mod; }
  inline void Add(int &a, int b) { a = a + b < mod ? a + b : a + b - mod; }
  inline void Dec(int &a, int b) { a = a < b? a - b + mod : a - b; }
  inline void Mul(int &a, int b) { a = (ll) a * b % mod; }
  inline int ksm(int a, int p) {
    for (ret = 1; p; p >>= 1, Mul(a, a)) (p & 1) && (Mul(ret, a), 1);
    return ret;
  }
  inline int Inv(int a) { return ksm(a, mod - 2); }
  inline int sqr(int a) { return (ll) a * a % mod; }
  inline int cub(int a) { return (ll) a * a % mod * a % mod; }
} using namespace modular;
template <typename T> inline void ckmax(T &a, T b) { a < b ? a = b : 0; }
template <typename T> inline void ckmin(T &a, T b) { a > b ? a = b : 0; }
template <typename T> inline T Abs(T a) { return a < 0 ? -a : a; }
template <typename T> inline T gcd(T a, T b) {
  T t;
  while (b) t = a, a = b, b = t - t / a * a;
  return a;
}
int invv[23], lim, tim;
poly rev[23], w[23];
inline void init_w(int lm = 1 << 18) {
  w[18].rez(lm), w[18][0] = 1, w[18][1] = ksm(3, (mod - 1) >> 19);
  for (ri i = 2; i < lm; ++i) w[18][i] = mul(w[18][i - 1], w[18][1]);
  for (ri i = 17; ~i; --i) {
    w[i].rez(lm >>= 1);
    for (ri j = 0; j < lm; ++j) w[i][j] = w[i + 1][j << 1];
  }
}
inline void init_r(int up) {
  for (lim = 1, tim = 0; lim < up; lim <<= 1, ++tim);
  if (rev[tim].size()) return;
  rev[tim].rez(lim), invv[tim] = Inv(lim);
  for (ri i = 1; i < lim; ++i) rev[tim][i] = (rev[tim][i >> 1] >> 1) | ((i & 1) << (tim - 1)); 
}
inline void ntt(poly &A, int typ) {
  static ulll a[1 << 20 | 5];
  for (ri i = 0; i < lim; ++i) a[rev[tim][i]] = A[i];
  for (ri i = 1, t = 0, tp; i < lim; i <<= 1, ++t) for (ri j = 0; j < lim; j += i << 1) {
    #define work(x)\
    {\
      tp = mul(a[j + k + i + x] % mod, w[t][k + x]);\
      a[j + k + i + x] = a[j + k + x] + mod - tp;\
      a[j + k + x] += tp;\
    }
    if (i < 8) for (ri k = 0; k < i; ++k) work(0)
    else for (ri k = 0; k < i; k += 8) {
      work(0); work(1); work(2); work(3);
      work(4); work(5); work(6); work(7);
    }
  }
  for (ri i = 0; i < lim; ++i) A[i] = a[i] % mod;
  if (~typ) return;
  reverse(++A.begin(), A.end());
  for (ri i = 0; i < lim; ++i) Mul(A[i], invv[tim]);
}
inline poly operator * (poly a, poly b) {
  int n = a.size(), m = b.size(), t = n + m - 1;
  if (n <= 30 || m <= 30) {
    poly c(t);
    for (ri i = 0, trs; i < n; ++i) if ((trs = a[i])) for (ri j = 0; j < m; ++j) Add(c[i + j], mul(trs, b[j]));
    return c;
  }
  init_r(t);
  a.rez(lim), ntt(a, 1);
  b.rez(lim), ntt(b, 1);
  for (ri i = 0; i < lim; ++i) Mul(a[i], b[i]);
  return ntt(a, -1), a.rez(t), a;
}
inline void operator -= (poly &a, poly b) {
  int n = b.size();
  if (a.size() < n) a.rez(n);
  for (ri i = 0; i < n; ++i) Dec(a[i], b[i]);
}
const int N = 1e5 + 5;
int n, m, K, a[N], fac[N], ifac[N];
inline poly solve(int l, int r) {
  if (l == r) {
    poly ret(a[l] + 1);
    ret[a[l]] = 1;
    ret[0] = mod - 1;
    return ret;
  }
  int mid = (l + r) >> 1;
  return solve(l, mid) * solve(mid + 1, r);
}
inline void init_fac() {
  fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
  for (ri i = 2; i <= 100000; ++i) {
    fac[i] = mul(fac[i - 1], i);
  }
  ifac[100000] = Inv(fac[100000]);
  for (ri i = 99999; i > 1; --i) {
    ifac[i] = mul(ifac[i + 1], i + 1); 
  }
}
inline int C(int n, int m) {
  return mul(mul(fac[n], ifac[m]), ifac[n - m]);
}
int main() {
  #ifdef ldxcaicai
  freopen("lx.in", "r", stdin);
  #endif
  init_w();
  init_fac();
  n = read();
  m = read();
  K = read();
  for (ri i = 1; i <= m; ++i) {
    a[i] = read();
  }
  random_shuffle(a + 1, a + m + 1);
  poly ans = solve(1, m);
  int ss = 0;
  for (ri i = K; i <= n; ++i) {
    Add(ss, mul(C(i, K), ans[i]));
  }
  cout << ss << '\n';
  return 0;
}