#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const ll MOD=1e9+7; vector> matrixmul(int l, int m, int n, vector> a, vector> b){ vector> c(l, vector(n)); for(int i=0; i> matrixpow(int n, vector> a, ll k){ vector> ap=a, ans(n, vector(n)); for(int i=0; i>=1; } return ans; } ll powmod(ll a, ll k){ ll ap=a, ans=1; while(k){ if(k&1){ ans*=ap; ans%=MOD; } ap=ap*ap; ap%=MOD; k>>=1; } return ans; } ll inv(ll a){ return powmod(a, MOD-2); } int main() { int n, m; ll k; ll p, q; cin>>n>>m>>k>>p>>q; ll b[100010]; for(int i=0; i>b[i]; } p=p*inv(q)%MOD; vector> mat(2, vector(2)); mat[0][0]=mat[1][1]=(1-p+MOD)%MOD; mat[0][1]=mat[1][0]=p; auto matp=matrixpow(2, mat, k); ll ans=0; for(int i=0; i