#include #include #include #include #include #include #include using namespace std; using i64 = long long; const int NMAX = 100; const int AMAX = 100000; vector A; int N, M, C, sumA; i64 powmod(i64 a, i64 n, i64 p) { if (n == 0) return 1; return powmod(a * a % p, n / 2, p) * (n % 2 == 1 ? a : 1) % p; } i64 inv(i64 a, i64 p) { return powmod(a, p - 2, p); } bool is_prime(int a) { for (int div = 2; div * div <= a; ++div) if (a % div == 0) return false; return true; } int primitive_root(int p) { vector div; for (int i = 2; i * i <= p - 1; ++i) { if ((p - 1) % i == 0) { div.push_back(i); div.push_back((p - 1) / i); } } for (int i = 1; i < p - 1; ++i) { bool ok = true; for (int d : div) { ok &= powmod(i, d, p) != 1; } if (ok) return i; } } int garner(vector& a, vector& mods, int m) { int n = a.size(); vector b; auto gen_base = [&mods](int mod) { vector base{ 1 }; for (int j = 0; j < mods.size(); ++j) { base.push_back(base.back() * mods[j] % mod); } return base; }; auto f = [&b](vector base, int mod) { i64 x = 0; for (int j = 0; j < b.size(); ++j) { x += b[j] * base[j]; } x %= mod; return x; }; for (int i = 0; i < n; ++i) { auto base = gen_base(mods[i]); b.push_back(inv(base[i], mods[i]) * (-f(base, mods[i]) + a[i]) % mods[i]); if (b[i] < 0) b[i] += mods[i]; } return (int) f(gen_base(m), m); } void solve(int mod, vector& ans) { int g = primitive_root(mod); int r = powmod(g, (mod - 1) / C, mod); int zeta = 1; for (int i = 0; i < C; ++i, zeta = zeta * r % mod) { vector f(ans.size()); f[0] = 1; int upper = 0; for (int a : A) { for (int j = upper; j >= 0; --j) if (f[j] != 0) { f[j + a] += zeta * f[j]; f[j + a] %= mod; } upper += a; } for (int j = 0; j < ans.size(); ++j) ans[j] += f[j]; } for (int i = 0; i < ans.size(); ++i) ans[i] %= mod; ans[0] -= C; int invC = inv(C, mod); for (int i = 0; i < ans.size(); ++i) ans[i] = invC * ans[i] % mod; } int main() { cin >> N >> M >> C; assert(1 <= N && N <= 90); assert(2 <= M && M <= 1e9); assert(1 <= C && C <= N); A.resize(N); for (int i = 0; i < N; ++i) cin >> A[i]; for (int a : A) sumA += a; for (int a : A) assert(1 <= a); assert(1 <= sumA && sumA <= 1e5); bool reversed = 2 * C < N; if (reversed) C = N - C; vector mods; int num = 7; for (int m = 14000 / C * C + 1; mods.size() != num; m += C) { if (is_prime(m)) { mods.push_back(m); } } vector> x(num, vector(sumA + 1)); for (int i = 0; i < mods.size(); ++i) { solve(mods[i], x[i]); } vector ans(sumA + 1); for (int i = 0; i <= sumA; ++i) { vector a; for (int j = 0; j < mods.size(); ++j) a.push_back(x[j][i]); ans[i] = garner(a, mods, M); } if (reversed) { for (int i = 0; i <= sumA / 2; ++i) { swap(ans[i], ans[sumA - i]); } } if (N == 2 * C) ans[sumA] -= 1; for (int i = 1; i <= sumA; ++i) printf("%d%c", ans[i], i == sumA ? '\n' : ' '); }