#include #include namespace nachia{ template struct PrimitiveRoot{ static constexpr unsigned long long powm(unsigned long long a, unsigned long long i) { unsigned long long res = 1, aa = a; while(i){ if(i & 1) res = res * aa % MOD; aa = aa * aa % MOD; i /= 2; } return res; } static constexpr bool examine_val(unsigned int g){ unsigned int t = MOD - 1; for(unsigned long long d=2; d*d<=t; d++) if(t % d == 0){ if(powm(g, (MOD - 1) / d) == 1) return false; while(t % d == 0) t /= d; } if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false; return true; } static constexpr unsigned int get_val(){ for(unsigned int x=2; x #include #include using namespace std; using i64 = long long; using u64 = unsigned long long; using m32 = atcoder::static_modint<998244353>; #define rep(i,n) for(int i=0; i<(int)(n); i++) // a^i mod MOD template u64 powm(u64 a, u64 i) { if (i == 0) return 1; u64 r = powm(a * a % MOD, i / 2); if (i & 1) r = r * a % MOD; return r; } template void NTT(vector& A) { int N = 1; while (N < (int)A.size()) N *= 2; for (int i = 0, j = 0; j < N; j++) { if (i < j) swap(A[i], A[j]); for (int k = N >> 1; k > (i ^= k); k >>= 1); } for (int i = 1; i < N; i <<= 1) { u64 q = powm(g, (MOD - 1) / i / 2), qj = 1; for (int j = 0; j < i; j++) { for (int k = j; k < N; k += i * 2) { u64 l = A[k]; u64 r = A[k + i] * qj % MOD; A[k] = l + r; if (A[k] >= MOD) A[k] -= MOD; A[k + i] = l + MOD - r; if (A[k + i] >= MOD) A[k + i] -= MOD; } qj = qj * q % MOD; } } } template vector convolution(const vector& A, const vector& B) { int Z = 1; while (Z < (int)(A.size() + B.size())) Z *= 2; vector Ax(Z), Bx(Z); u64 iZ = powm(Z, MOD - 2); rep(i, A.size()) Ax[i] = A[i]; rep(i, B.size()) Bx[i] = B[i]; NTT(Ax); NTT(Bx); rep(i, Z) Ax[i] = Ax[i] * Bx[i] % MOD; NTT(Ax); reverse(Ax.begin() + 1, Ax.end()); rep(i, Z) Ax[i] = Ax[i] * iZ % MOD; Ax.resize(A.size() + B.size() - 1); return move(Ax); } template vector powsumFPS(const vector& A, int n) { if (n == 0) { return {}; } if (n == 1) { return { 1 }; } int N = 1; while (N < n) N *= 2; int hN = N / 2; vector hInv = powsumFPS(A, hN); vector tgA(N, 0); for (int i = 0; i < min(N, (int)A.size()); i++) tgA[i] = A[i]; NTT(tgA); vector htInv(N, 0); for (int i = 0; i < hN; i++) htInv[i] = hInv[i]; NTT(htInv); vector R(N); for (int i = 0; i < N; i++) R[i] = tgA[i] * htInv[i] % MOD; NTT(R); reverse(R.begin() + 1, R.end()); for (int i = 0; i < hN; i++) R[i] = R[hN + i]; for (int i = hN; i < N; i++) R[i] = 0; NTT(R); u64 iNN = powm((u64)N * N % MOD, MOD - 2); for (int i = 0; i < N; i++) R[i] = R[i] * htInv[i] % MOD * iNN % MOD; NTT(R); reverse(R.begin() + 1, R.end()); hInv.resize(n, 0); for (int i = hN; i < n; i++) hInv[i] = R[i - hN]; return move(hInv); } template vector invFPS(const vector& A, int n) { u64 iA0 = powm(A[0], MOD - 2); vector xA(min(n, (int)A.size())); for (int i = 0; i < (int)xA.size(); i++) xA[i] = (MOD - A[i]) * iA0 % MOD; xA[0] = 0; xA = powsumFPS(xA, n); for (int i = 0; i < (int)xA.size(); i++) xA[i] = xA[i] * iA0 % MOD; return move(xA); } static vector InvMOD = { 1,1 }; template vector logFPS(const vector& A, int n) { int z = A.size(); for (int i = InvMOD.size(); i <= n; i++) { InvMOD.push_back((MOD - MOD / i) * InvMOD[MOD % i] % MOD); } auto res = invFPS(A, n); vector Abuf(z); rep(i, z - 1) Abuf[i] = A[i + 1] * (i + 1) % MOD; res = convolution(res, Abuf); res.resize(n); for (int i = n - 2; i >= 0; i--) res[i + 1] = res[i] * InvMOD[i + 1] % MOD; res[0] = 0; return res; } template vector expFPS(const vector& A, int n) { vector res = { 1 }; while ((int)res.size() < n) { int z = res.size(); auto tmp = logFPS(res, z * 2); tmp[0] = MOD - 1; rep(i, min(z * 2, A.size())) { tmp[i] = MOD - tmp[i] + A[i]; if (tmp[i] >= MOD) tmp[i] -= MOD; } res = convolution(res, tmp); res.resize(min(n, 2 * z)); } return res; } template vector powFPS(const vector& A, u64 k) { int n = A.size(); int zerocnt = 0; rep(i, n) if (A[i] == 0) zerocnt = i + 1; else break; if (zerocnt >= (n - 1) / k + 1) return vector(n, 0); auto res = A; rep(i, n - zerocnt) res[i] = res[i + zerocnt]; i64 A0 = res[0]; i64 iA0 = powm(A0, MOD - 2); i64 pA0 = powm(A0, k); rep(i, n) res[i] = res[i] * iA0 % MOD; res = logFPS(res, n); rep(i, n) res[i] = res[i] * k % MOD; res = expFPS(res, n); rep(i, n) res[i] = res[i] * pA0 % MOD; zerocnt *= k; res.resize(n); for (int i = n - 1; i >= zerocnt; i--) res[i] = res[i - zerocnt]; rep(i, zerocnt) res[i] = 0; return res; } template vector SubsetSum(const vector& D) { int n = D.size(); for (int i = InvMOD.size(); i <= n; i++) { InvMOD.push_back((MOD - MOD / i) * InvMOD[MOD % i] % MOD); } vector A(n); for (int i = 1; i < n; i++) if (D[i] != 0) { u64 tmp = i * D[i] % MOD; for (int a = i; a < n; a += i) { A[a] = (A[a] + tmp * InvMOD[a]) % MOD; tmp = MOD - tmp; } } rep(i, n + 1) A[i] %= MOD; A = expFPS(A, n); return A; } template vector PolynomialTaylorShift(vector A, u64 c){ u64 n = A.size(); vector factorial(n+1, 1); for(u64 i=1; i<=n; i++) factorial[i] = ((u64)factorial[i-1] * i) % MOD; vector invfactorial(n+1, 1); invfactorial[n] = powm(factorial[n], MOD-2); for(u64 i=n; i>=1; i--) invfactorial[i-1] = ((u64)invfactorial[i] * i) % MOD; vector C(n, 1); for(u64 i=1; i(A, C); for(u64 i=0; i // <998244353,3> // <1107296257,10> // <2113929217,5> const int INF = 1001001; const u64 MOD = 998244353; const u64 g = nachia::PrimitiveRoot::val; int main(){ int N,M; cin >> N >> M; vector A(N); vector B(N); vector C(N); rep(i,N) cin >> A[i] >> B[i] >> C[i]; u64 off = 1; rep(i,N) off *= powm(A[i], C[i]); rep(i,N) B[i] = B[i] * powm(A[i], MOD-2) % MOD; vector fact(M+1, 1); for(int i=1; i<=M; i++) fact[i] = fact[i-1] * i % MOD; vector ifact(M+1, 1); ifact[M] = powm(fact[M], MOD-2); for(int i=M; i>=1; i--) ifact[i-1] = ifact[i] * i % MOD; vector inv(M+1, 1); for(int i=1; i<=M; i++) inv[i] = ifact[i] * fact[i-1] % MOD; vector ExK; { vector> Fup, Fdown; rep(i,N){ Fup.push_back(vector{ B[i] * C[i] % MOD }); Fdown.push_back(vector{ u64(1), B[i] }); } for(int i=0; i+1<(int)Fup.size(); i += 2){ vector u1 = convolution(Fup[i], Fdown[i+1]); vector u2 = convolution(Fup[i+1], Fdown[i]); if(u1.size() < u2.size()) swap(u1, u2); rep(i,u2.size()) u1[i] = (u1[i] + u2[i]) % MOD; Fdown.push_back(convolution(Fdown[i], Fdown[i+1])); Fup.push_back(move(u1)); } auto Frac = convolution(Fup.back(), invFPS(Fdown.back(), M+1)); Frac.resize(M+1, 0); for(int i=M; i>=1; i--) Frac[i] = Frac[i-1] * inv[i] % MOD; Frac[0] = 0; ExK = expFPS(Frac, M+1); } ExK = PolynomialTaylorShift(ExK, MOD - 1); { vector> Fup, Fdown; rep(i,M+1){ Fup.push_back(vector{ ExK[i] }); Fdown.push_back(vector{ u64(1), (MOD-i) % MOD }); } for(int i=0; i+1<(int)Fup.size(); i += 2){ vector u1 = convolution(Fup[i], Fdown[i+1]); vector u2 = convolution(Fup[i+1], Fdown[i]); if(u1.size() < u2.size()) swap(u1, u2); rep(i,u2.size()) u1[i] = (u1[i] + u2[i]) % MOD; Fdown.push_back(convolution(Fdown[i], Fdown[i+1])); Fup.push_back(move(u1)); } ExK = convolution(Fup.back(), invFPS(Fdown.back(), M+1)); } auto ans = ExK; rep(i,M+1) ans[i] = ans[i] * off % MOD; for(int i=1; i<=M; i++) cout << ans[i] << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;