// yukicoderではつけるとなんか壊れる // #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; // verify: https://judge.yosupo.jp/submission/153840 vector fps_inv(vector f,int deg = -1){ if(deg==-1) deg = f.size() - 1; assert(f.size()); assert(f[0].val()!=0); vector g = {(mint)1/f[0]}; for(int i=1;i<=deg;i<<=1){ vector h = convolution(g,f); h.resize(2*i); for(mint &u:h) u = -u; h[0] += 2; g = convolution(g,h); g.resize(2*i); } g.resize(deg + 1); return g; } vector new_inv(vector f,int deg = -1){ if(deg==-1) deg = f.size() - 1; assert(f.size()); assert(f[0].val()!=0); vector g = {(mint)1/f[0]}; vector ff = {f[0]}; for(int i=1;i<=deg;i<<=1){ // iでmod x^(2i)を計算する for(int j=ff.size();j h = convolution(g,ff); h.resize(2*i); for(mint &u:h) u = -u; h[0] += 2; g = convolution(g,h); g.resize(2*i); } g.resize(deg + 1); return g; } vector fps_derivative(vector &f){ vector ret; for(int i=1;i fps_integral(vector &f){ vector g(f.size()); for(int i=g.size() - 1;i>=1;i--){ g[i] = f[i - 1]/(mint)(i); } g[0] = 0; return g; } // get log(f) = -sum (1 - f)^n/n vector fps_log(vector f,int deg = -1){ if(deg==-1) deg = f.size() - 1; assert(f[0].val()==1); vector g = convolution(fps_derivative(f),fps_inv(f,deg)); g.resize(deg + 1); return fps_integral(g); } // get exp(f) = sum f^i/i! vector fps_exp(vector f,int deg = -1){ if(deg==-1) deg = f.size() - 1; assert(f.size()); assert(f[0].val()==0); vector g = {(mint)1}; for(int i=1;i<=deg;i<<=1){ vector h(2*i); h[0] = 1; vector log_g = fps_log(g,h.size() - 1); for(int j=0;j shift(vector ff,int d){ int i,len = ff.size(); vector f1(len + 1),f2(len + 1); mint x = 1; for(i=0;i f3 = convolution(f1,f2); vector ret; for(i=len;i<2*len;i++){ ret.push_back(f3[i]*fi[i - len]); } return ret; } // input: s[0] + s[1]x + ... s[n - 1]x^n - 1 // output: (c[0] - c[1] - .. c[d])s = 0かつc[0] = 1なるcを存在すればどれか一つ // copied from: https://nyaannyaan.github.io/library/fps/berlekamp-massey.hpp // verified: https://judge.yosupo.jp/submission/199848 // algorithmの気持ち // deg(c) = kの時に s[i] + Σ_{j vector BerlekampMassey(const vector &s) { const int N = (int)s.size(); vector b, c; b.reserve(N + 1); c.reserve(N + 1); b.push_back(mint(1)); c.push_back(mint(1)); mint y = mint(1); for(int ed = 1; ed <= N; ed++){ int l = int(c.size()), m = int(b.size()); mint x = 0; for (int i = 0; i < l; i++) x += c[i] * s[ed - l + i]; b.emplace_back(mint(0)); m++; if(x == mint(0)) continue; mint freq = x / y; if(l < m){ auto tmp = c; c.insert(begin(c), m - l, mint(0)); for (int i = 0; i < m; i++) c[m - 1 - i] -= freq * b[m - 1 - i]; b = tmp; y = x; }else{ for (int i = 0; i < m; i++) c[l - 1 - i] -= freq * b[m - 1 - i]; } } reverse(begin(c), end(c)); return c; } // BostanMori // input: P(x)/Q(x),deg(P(x)) P,vector Q,ll N){ while(N){ vector _Q(Q.size()); for(int i=0;i nP = convolution(P,_Q); vector nQ = convolution(Q,_Q); Q.resize(nQ.size()/2 + 1); for(int i=0;i sparse_pow(vector &f,int k,int N){ assert(f.size()); assert(f[0]!=0); mint iv = pw(f[0],mod - 2); vector> ff; for(int i=1;i ret(N); ret[0] = pw(f[0],k); for(int i=1;ii) break; ret[i] += ff[j].second*deg*ret[i - deg]; } ret[i] *= k; for(int j=0;ji) break; ret[i] -= ff[j].second*(i - deg)*ret[i - deg]; } ret[i] *= inv[i]; } return ret; } int main(){ int p1,p2,q1,q2,t; cin >> p1 >> p2 >> q1 >> q2 >> t; mint p = (mint)p1/(mint)p2; mint q = (mint)q1/(mint)q2; vector g(t + 2),h(t + 1); mint pr = 1,a = q; for(int i=0;i<=t;i++){ g[i + 1] = -pr; h[i] = pr; pr *= a; a *= q; } g[0] = 1; for(int i=1;i<=t;i++) g[i] *= p; // vector f = convolution(fps_inv(g),h); // cout << f[t].val() << "\n"; vector ff = new_inv(g); mint ans = 0; for(int i=0;i<=t;i++) ans += ff[i]*h[t - i]; cout << ans.val() << "\n"; // for(int i=0;i<=2;i++) cout << (g[i]*8).val() << " "; // cout << "\n"; // for(int i=0;i<=2;i++) cout << (h[i]*64).val() << " "; // cout << "\n"; }