/** * date : 2022-05-23 22:01:31 */ #define NDEBUG #include #include #include #include #include using i128 = __int128_t; namespace atcoder { namespace internal { // @param m `1 <= m` // @return x mod m constexpr i128 safe_mod(i128 x, i128 m) { x %= m; if (x < 0) x += m; return x; } // @param b `1 <= b` // @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g constexpr std::pair inv_gcd(i128 a, i128 b) { a = safe_mod(a, b); if (a == 0) return {b, 0}; // Contracts: // [1] s - m0 * a = 0 (mod b) // [2] t - m1 * a = 0 (mod b) // [3] s * |m1| + t * |m0| <= b i128 s = b, t = a; i128 m0 = 0, m1 = 1; while (t) { i128 u = s / t; s -= t * u; m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b // [3]: // (s - t * u) * |m1| + t * |m0 - m1 * u| // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u) // = s * |m1| + t * |m0| <= b auto tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } // by [3]: |m0| <= b/g // by g != b: |m0| < b/g if (m0 < 0) m0 += b / s; return {s, m0}; } } // namespace internal } // namespace atcoder namespace atcoder { i128 inv_mod(i128 x, i128 m) { assert(1 <= m); auto z = internal::inv_gcd(x, m); assert(z.first == 1); return z.second; } // (rem, mod) std::pair crt(const std::vector& r, const std::vector& m) { assert(r.size() == m.size()); int n = int(r.size()); // Contracts: 0 <= r0 < m0 i128 r0 = 0, m0 = 1; for (int i = 0; i < n; i++) { assert(1 <= m[i]); i128 r1 = internal::safe_mod(r[i], m[i]), m1 = m[i]; if (m0 < m1) { std::swap(r0, r1); std::swap(m0, m1); } if (m0 % m1 == 0) { if (r0 % m1 != r1) return {0, 0}; continue; } // assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1) // (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1)); // r2 % m0 = r0 // r2 % m1 = r1 // -> (r0 + x*m0) % m1 = r1 // -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1) // -> x = (r1 - r0) / g * inv(u0) (mod u1) // im = inv(u0) (mod u1) (0 <= im < u1) i128 g, im; std::tie(g, im) = internal::inv_gcd(m0, m1); i128 u1 = (m1 / g); // |r1 - r0| < (m0 + m1) <= lcm(m0, m1) if ((r1 - r0) % g) return {0, 0}; // u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1) i128 x = (r1 - r0) / g % u1 * im % u1; // |r0| + |m0 * x| // < m0 + m0 * (u1 - 1) // = m0 + m0 * m1 / g - m0 // = lcm(m0, m1) r0 += x * m0; m0 *= u1; // -> lcm(m0, m1) if (r0 < 0) r0 += m0; } return {r0, m0}; } } // namespace atcoder #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define rep1(i, n) for (int i = 1; i <= (n); i++) #define repr(i, n) for (int i = (n)-1; i >= 0; i--) using u8 = uint8_t; using i128 = __int128_t; u8 dp[92][100064]; u8 res[100064]; i128 ans[100064]; int a[92], N, mod, C; void calc(char M) { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; int S = accumulate(a, a + N, 0); rep(k, N) { int x = a[k]; repr(i, N + 1) rep(j, S + 1) { dp[i + 1][j + x] += dp[i][j]; if (dp[i + 1][j + x] >= M) dp[i + 1][j + x] -= M; } } rep1(i, S) res[i] = dp[C][i]; } int main() { scanf("%d %d %d\n", &N, &mod, &C); rep(i, N) scanf("%d", &a[i]); int S = accumulate(a, a + N, 0); i128 curmod = 1; vector m(2), r(2); for (int p : { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, }) { m[0] = curmod, m[1] = p; calc(p); if (p == 2) { rep(i, S + 1) ans[i] = res[i]; curmod = p; continue; } rep(i, S + 1) { r[0] = ans[i], r[1] = res[i]; ans[i] = atcoder::crt(r, m).first; } curmod *= p; } rep1(i, S) { printf("%d", int(ans[i] % mod)); printf(i == S ? "\n" : " "); } }