#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 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"; // 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"; }