#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; template struct modint { private: unsigned int value; static constexpr int mod() {return m;} public: constexpr modint(const long long x = 0) noexcept { long long y = x; if(y < 0 || y >= mod()) { y %= mod(); if(y < 0) y += mod(); } value = (unsigned int)y; } static constexpr int get_mod() noexcept {return m;} static constexpr int primitive_root() noexcept { assert(m == 998244353); return 3; } constexpr unsigned int val() noexcept {return value;} constexpr modint &operator+=(const modint &other) noexcept { value += other.value; if(value >= mod()) value -= mod(); return *this; } constexpr modint &operator-=(const modint &other) noexcept { unsigned int x = value; if(x < other.value) x += mod(); x -= other.value; value = x; return *this; } constexpr modint &operator*=(const modint &other) noexcept { unsigned long long x = value; x *= other.value; value = (unsigned int) (x % mod()); return *this; } constexpr modint &operator/=(const modint &other) noexcept { return *this *= other.inverse(); } constexpr modint inverse() const noexcept { assert(value); long long a = value,b = mod(),x = 1,y = 0; while(b) { long long q = a/b; a -= q*b; swap(a,b); x -= q*y; swap(x,y); } return modint(x); } constexpr modint power(long long N) const noexcept { assert(N >= 0); modint p = *this,ret = 1; while(N) { if(N & 1) ret *= p; p *= p; N >>= 1; } return ret; } constexpr modint operator+() {return *this;} constexpr modint operator-() {return modint() - *this;} constexpr modint &operator++(int) noexcept {return *this += 1;} constexpr modint &operator--(int) noexcept {return *this -= 1;} friend modint operator+(const modint& lhs, const modint& rhs) {return modint(lhs) += rhs;} friend modint operator-(const modint& lhs, const modint& rhs) {return modint(lhs) -= rhs;} friend modint operator*(const modint& lhs, const modint& rhs) {return modint(lhs) *= rhs;} friend modint operator/(const modint& lhs, const modint& rhs) {return modint(lhs) /= rhs;} friend ostream &operator<<(ostream &os,const modint &x) {return os << x.value;} }; using mint = modint<998244353>; /* using mint = modint<1000000007>; */ int ceil_log2(int n) { int res = 0; while((1U << res) < (unsigned int)n) { res++; } return res; } template void Butterfly(vector &a,bool inverse = false) { int N = (int)a.size(); int H = __builtin_ctz(N); assert(N == (1 << H)); static constexpr int pr = mint::primitive_root(); static bool first_call = true; static vector w(30),iw(30); if(first_call) { first_call = false; int cnt = __builtin_ctz(mint::get_mod() - 1); mint e = mint(pr).power((mint::get_mod() - 1) >> cnt); mint ie = e.inverse(); for(int i = cnt;i >= 1;i--) { w[i] = e; iw[i] = ie; e *= e; ie *= ie; } } if(!inverse) { int width = N; int log = H; const mint im = w[2]; while(width > 1) { mint cur = w[log]; if(width == 2) { int offset = width >> 1; for(int i = 0;i < N;i += width) { mint root = 1; for(int j = i;j < i + offset;j++) { mint s = a[j],t = a[j + offset]; a[j] = s + t; a[j + offset] = (s - t) * root; root *= cur; } } width >>= 1; log--; } else { int offset = width >> 2; for(int i = 0;i < N;i += width) { mint root = 1; for(int j = i;j < i + offset;j++) { mint root2 = root * root; mint root3 = root2 * root; mint s = a[j],t = a[j + offset],u = a[j + offset * 2],v = a[j + offset * 3]; mint spu = s + u; mint smu = s - u; mint tpv = t + v; mint tmvim = (t - v) * im; a[j] = spu + tpv; a[j + offset] = (spu - tpv) * root2; a[j + offset * 2] = (smu + tmvim) * root; a[j + offset * 3] = (smu - tmvim) * root3; root *= cur; } } width >>= 2; log -= 2; } } } else { int width = H & 1 ? 2 : 4; int log = H & 1 ? 1 : 2; const mint im = iw[2]; while(width <= N) { mint cur = iw[log]; if(width == 2) { int offset = width >> 1; for(int i = 0;i < N;i += width) { mint root = 1; for(int j = i;j < i + offset;j++) { mint s = a[j],t = a[j + offset] * root; a[j] = s + t; a[j + offset] = s - t; root *= cur; } } } else { int offset = width >> 2; for(int i = 0;i < N;i += width) { mint root = 1; for(int j = i;j < i + offset;j++) { mint root2 = root * root; mint root3 = root2 * root; mint s = a[j],t = a[j + offset] * root2,u = a[j + offset * 2] * root,v = a[j + offset * 3] * root3; mint spt = s + t; mint smt = s - t; mint upv = u + v; mint umvim = (u - v) * im; a[j] = spt + upv; a[j + offset] = smt + umvim; a[j + offset * 2] = spt - upv; a[j + offset * 3] = smt - umvim; root *= cur; } } } width <<= 2; log += 2; } } } template vector Convolution(vector a,vector b) { int N = (int)a.size(),M = (int)b.size(); if(min(N,M) <= 60) { vector res(N + M - 1); if(N < M) { swap(N,M); swap(a,b); } for(int i = 0;i < N;i++) { for(int j = 0;j < M;j++) { res[i + j] += a[i] * b[j]; } } return res; } int L = 1 << ceil_log2(N + M - 1); a.resize(L); b.resize(L); Butterfly(a); Butterfly(b); for(int i = 0;i < L;i++) { a[i] *= b[i]; } Butterfly(a,true); a.resize(N + M - 1); const mint invL = mint(L).inverse(); for(int i = 0;i < N + M - 1;i++) { a[i] *= invL; } return a; } void Main() { mint P,Q; { int p1,p2; cin >> p1 >> p2; P = mint(p1) / p2; } { int q1,q2; cin >> q1 >> q2; Q = mint(q1) / q2; } int N; cin >> N; vector q(N + 1); q[0] = 1; for(int i = 1;i <= N;i++) { q[i] = q[i - 1] * Q; } for(int i = 1;i <= N;i++) { q[i] *= q[i - 1]; } vector g(N + 1); g[0] = 1; for(int i = 1;i <= N;i++) { g[i] = -P * q[i - 1]; } vector h(1); h[0] = 1; int k = 1; while(k - 1 < N) { vector nh = h; for(int i = 0;i < (int)h.size();i++) { nh[i] *= 2; } h = Convolution(h,h); h = Convolution(h,g); h.resize(k << 1); nh.resize(h.size()); for(int i = 0;i < (int)h.size();i++) { nh[i] -= h[i]; } swap(h,nh); k <<= 1; } mint ans = 0; for(int i = 0;i <= N;i++) { ans += q[N - i] * h[i]; } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) Main(); }