显然，就是有一些的 OGF 为 \(\frac{1}{1 - x}\)，有一些为 \(\frac{1 - x^{b_i + 1}}{1 - x}\)。乘起来即可。
发现不太好算分子，考虑枚举哪些算了。
然后我们考虑 \(2^t\) 的枚举子集。然后直接乘上对应的 \(b_i + 1\) 的系数即可。
然后我们要求分母第 \(i\) 位的系数，这个很典， \(i\) 个无标号元素放入，\(n\) 个有标号集合里的方案。直接插板即可。
\[\binom{n + i - 1}{i}
\]
然后我们答案要对这个求 \(1 \to k\) 的前缀和，那么我们直接用典恒等式有：
\[\binom{n + k}{n}
\]
然后我们对于这个直接用 Lucas 求即可。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define cpy(x, y, s) memcpy(x, y, sizeof(x[0]) * (s))
#define mem(x, k) memset(x, k, sizeof(x))
#define ll long long
#define int long long
// \yhx-12243/ 鱼大保佑！！
using namespace std;
const int _ = 1e6 + 5;
int power (int x, int y, int mod) {
int res = 1;
for ( ; y; x = x * x % mod, y >>= 1)
if (y & 1) res = res * x % mod;
return res;
}
int n, m, t, p, b[_];
int inv[_], fac[_], res;
int C (int n, int m) {
return fac[n] * inv[m] % p * inv[n - m] % p;
}
int lucas (int n, int m) {
if (n < m) return 0;
if (n < p) return C(n, m);
return lucas(n / p, m / p) * lucas(n % p, m % p) % p;
}
signed main () {
cin >> n >> t >> m >> p;
rep(i, 0, t - 1) cin >> b[i], b[i] ++;
fac[0] = inv[0] = 1;
rep(i, 1, p - 1) fac[i] = fac[i - 1] * i % p;
rep(i, 1, p - 1) inv[i] = power(fac[i], p - 2, p);
rep(i, 0, (1 << t) - 1) {
int f = 1, sum = 0;
rep(j, 0, t - 1) if ((i >> j) & 1) {
sum += b[j], f = -f;
}
// cout << i << " " << sum << " " << n + m - sum << " " << m - sum << endl;
(res += f * lucas(n + m - sum, m - sum)) %= p;
}
cout << (res + p) % p;
return 0;
}