#line 1 "f.cpp" #include #line 3 "f.cpp" using namespace std; using ll=long long; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using pq_ = priority_queue, greater>; template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;} template T square(T a){return a * a;} #line 2 "/Users/Shared/po167_library/fps/FPS_composition.hpp" #include namespace po167{ // n = |g| // return f(g(x)) // https://maspypy.com/fps-合成・逆関数の解説(2)転置原理による合成ア template std::vector FPS_comp(std::vector f, std::vector g){ assert(g[0] == 0); auto rec = [&](auto rec, int n, int k, std::vector Q) -> std::vector { if (n == 1){ std::vector p(2 * k); std::reverse(f.begin(), f.end()); for (int i = 0; i < k; i++) p[2 * i] = f[i]; return p; } std::vector nxt_Q(2 * n * k); for (int i = 0; i < n * k; i++) nxt_Q[n * k + i] += Q[i * 2] * 2; Q.resize(4 * n * k); atcoder::internal::butterfly(Q); // Q(-x) std::vector R(4 * n * k); for (int i = 0; i < 2 * n * k; i++){ R[i * 2] = Q[i * 2 + 1]; R[i * 2 + 1] = Q[i * 2]; } T iz = (T)(1) / (T)(4 * n * k); for (int i = 0; i < 4 * n * k; i++) Q[i] *= R[i]; for (int i = 0; i < 2 * n * k; i++) Q[i] = Q[i * 2]; Q.resize(2 * n * k); atcoder::internal::butterfly_inv(Q); for (int i = 0; i < 2 * n * k; i++) nxt_Q[i] += Q[i] * iz * 2; for (int j = 0; j < 2 * k; j++) for (int i = n / 2; i < n; i++){ nxt_Q[n * j + i] = 0; } std::vector pq = rec(rec, n / 2, k * 2, nxt_Q); std::vector p(2 * n * k); for (int j = 0; j < 2 * k; j++) for (int i = n / 2; i < n; i++){ pq[n * j + i] = 0; } for (int i = 0; i < n * k; i++) p[i * 2 + 1] += pq[n * k + i]; std::reverse(pq.begin(), pq.end()); atcoder::internal::butterfly(pq); pq.resize(4 * n * k); for (int i = 2 * n * k - 1; i >= 0; i--){ pq[i * 2 + 1] = pq[i]; pq[i * 2] = pq[i]; } for (int i = 0; i < 4 * n * k; i++) pq[i] *= R[i]; atcoder::internal::butterfly_inv(pq); for (int i = 0; i < 2 * n * k; i++) p[i] += pq[4 * n * k - 1 - i] * iz; return p; }; int N = (int)g.size(); int n = 1; while (n < N) n *= 2; f.resize(n, 0); g.resize(n, 0); std::vector Q(2 * n); for (int i = 0; i < n; i++) Q[i] = -g[i]; auto p = rec(rec, n, 1, Q); std::vector res(n); for (int i = 0; i < n; i++) res[i] = p[i]; std::reverse(res.begin(), res.end()); res.resize(N); return res; } } #line 27 "f.cpp" using mint = atcoder::modint998244353; #line 2 "/Users/Shared/po167_library/math/Binomial.hpp" #line 5 "/Users/Shared/po167_library/math/Binomial.hpp" namespace po167{ template struct Binomial{ std::vector fact_vec, fact_inv_vec; void extend(int m = -1){ int n = fact_vec.size(); if (m == -1) m = n * 2; if (n >= m) return; fact_vec.resize(m); fact_inv_vec.resize(m); for (int i = n; i < m; i++){ fact_vec[i] = fact_vec[i - 1] * T(i); } fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1]; for (int i = m - 1; i > n; i--){ fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i); } } Binomial(int MAX = 0){ fact_vec.resize(1, T(1)); fact_inv_vec.resize(1, T(1)); extend(MAX + 1); } T fact(int i){ if (i < 0) return 0; while (int(fact_vec.size()) <= i) extend(); return fact_vec[i]; } T invfact(int i){ if (i < 0) return 0; while (int(fact_inv_vec.size()) <= i) extend(); return fact_inv_vec[i]; } T C(int a, int b){ if (a < b || b < 0) return 0; return fact(a) * invfact(b) * invfact(a - b); } T invC(int a, int b){ if (a < b || b < 0) return 0; return fact(b) * fact(a - b) *invfact(a); } T P(int a, int b){ if (a < b || b < 0) return 0; return fact(a) * invfact(a - b); } T inv(int a){ if (a < 0) return inv(-a) * T(-1); if (a == 0) return 1; return fact(a - 1) * invfact(a); } T Catalan(int n){ if (n < 0) return 0; return fact(2 * n) * invfact(n + 1) * invfact(n); } T narayana(int n, int k){ if (n <= 0 || n < k || k < 1) return 0; return C(n, k) * C(n, k - 1) * inv(n); } T Catalan_pow(int n,int d){ if (n < 0 || d < 0) return 0; if (d == 0){ if (n == 0) return 1; return 0; } return T(d) * inv(d + n) * C(2 * n + d - 1, n); } // retrun [x^a] 1/(1-x)^b T ruiseki(int a,int b){ if (a < 0 || b < 0) return 0; if (a == 0){ return 1; } return C(a + b - 1, b - 1); } // (a, b) -> (c, d) // always x + e >= y T mirror(int a, int b, int c, int d, int e = 0){ if (a + e < b || c + e < d) return 0; if (a > c || b > d) return 0; a += e; c += e; return C(c + d - a - b, c - a) - C(c + d - a - b, c - b + 1); } // return sum_{i = 0, ... , a} sum_{j = 0, ... , b} C(i + j, i) // return C(a + b + 2, a + 1) - 1; T gird_sum(int a, int b){ if (a < 0 || b < 0) return 0; return C(a + b + 2, a + 1) - 1; } // return sum_{i = a, ..., b - 1} sum_{j = c, ... , d - 1} C(i + j, i) // AGC 018 E T gird_sum_2(int a, int b, int c, int d){ if (a >= b || c >= d) return 0; a--, b--, c--, d--; return gird_sum(a, c) - gird_sum(a, d) - gird_sum(b, c) + gird_sum(b, d); } // the number of diagonal dissections of a convex n-gon into k+1 regions. // OEIS A033282 // AGC065D T diagonal(int n, int k){ if (n <= 2 || n - 3 < k || k < 0) return 0; return C(n - 3, k) * C(n + k - 1, k) * inv(k + 1); } }; } #line 29 "f.cpp" void solve(); // DEAR MYSTERIES / TOMOO int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ po167::Binomial table; ll N, M; int K; cin >> N >> M >> K; // 指定された x 個が入っている vector q(K + 1); /*{ vector tmp(N + 1); tmp[0] = 1; rep(i, 0, N) { tmp[i + 1] = tmp[i] * M; } rep(j, 0, K + 1) { q[j] = tmp[N] * table.C(M, j); vector tmp2(N + 1); rep(i, 0, N) tmp2[i + 1] += tmp[i] * (j + 1); rep(i, 0, N) tmp2[i + 1] += tmp2[i] * (M - j - 1); swap(tmp, tmp2); } }*/ rep(i, 0, K + 1) { q[i] = (mint(M - i)).pow(N); } { vector to(K + 1); rep(i, 0, K + 1) { q[i] *= table.invfact(i) * (i & 1 ? -1 : 1); to[i] = table.invfact(i); } auto tmp = atcoder::convolution(to, q); mint tmp2 = 1; rep(i, 0, K + 1) { q[i] = tmp[i] * tmp2; tmp2 *= M - i; } } vector ans(K + 1); /*// a 個の積 rep(a, 0, K + 1) { // pow b rep(b, a, K + 1) { { vector tmp(b + 1); tmp[0] = 1; rep(i, 0, b) { tmp[i + 1] = tmp[i] * a; } rep(j, 0, a) { vector tmp2(b + 1); rep(i, 0, b) tmp2[i + 1] += tmp[i] * (j + 1); rep(i, 0, b) tmp2[i + 1] += tmp2[i] * (a - j - 1); swap(tmp, tmp2); } mint val = tmp[b]; ans[b] += val * q[a]; } } }*/ vector e(K + 1); rep(i, 1, K + 1) e[i] = table.invfact(i); ans = po167::FPS_comp(q, e); rep(i, 1, K + 1) { ans[i] *= table.fact(i); cout << ans[i].val() << "\n"; } } /* * S(n, k) を n 個の区別できる要素を k 個の区別できないグループに分けることを考える * このとき、 * S(n, k) * x^{n}/n! = (e^{x} - 1)^{k} / k! * 本当は、S(n, k) ではなくて、 * T(n, k) = S(n, k) * P(M, k) なので * T(n, k) * x^{n} / n! = (e^{x} - 1)^{k} / k! * M! / (M - k)! * = (e^{x} - 1)^{k} * Binom(M, k) * うーん * 指定された x 個が入っているかを考える * pow k で、x 個の積になっているものを考える * * * */