#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(bn-r) r=n-r; if(r==0) return 1; ll a=1; //a=n!/(n-r)!=n~n-r+1までの総積->O(r) for(ll i=0;i vector> matplus(vector> a,vector> b){ asert(a.size()==b.size() and a[0].size()==b[0].size()); for(int i=0;i vector> matminus(vector> a,vector> b){ asert(a.size()==b.size() and a[0].size()==b[0].size()); for(int i=0;i vector> matmul(vector> a,vector> b){ assert(a[0].size()==b.size()); int n=b.size(); vector> ret(a.size(),vector(b[0].size(),0)); for(int i=0;i vector> matpow(vector> a,ll k){ assert(a.size()==a[0].size()); int n=a.size(); vector> ret(n,vector(n,0)); for(int i=0;i0){ if(k&1) ret=matmul(ret,a); a=matmul(a,a); k>>=1; } return ret; } //mod vector> matplus_mod(vector> a,vector> b){ assert(a.size()==b.size() and a[0].size()==b[0].size()); for(int i=0;i=mod) a[i][j]-=mod; } } return a; } vector> matminus_mod(vector> a,vector> b){ assert(a.size()==b.size() and a[0].size()==b[0].size()); for(int i=0;i> matmul_mod(vector> a,vector> b){ assert(a[0].size()==b.size()); int n=b.size(); vector> ret(a.size(),vector(b[0].size(),0)); for(int i=0;i> matpow_mod(vector> a,ll k){ assert(a.size()==a[0].size()); int n=a.size(); vector> ret(n,vector(n,0)); for(int i=0;i0){ if(k&1) ret=matmul_mod(ret,a); a=matmul_mod(a,a); k>>=1; } return ret; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); ll n,m,k,p,q;cin>>n>>m>>k>>p>>q; vector b(n); rep(i,n){ scanf("%lld",&b[i]); } //個別に入ってる確率が計算できればok ll ans=0; ll mov=p*inv_mod(q)%mod; ll sta=(q-p)*inv_mod(q)%mod; /* (in[i+1] ) = (sta mov) (in[i]) (out[i+1]) (mov sta) (out[i]) */ vector> mat(2,vector(2)); mat[0][0]=sta;mat[0][1]=mov;mat[1][0]=mov;mat[1][1]=sta; mat=matpow_mod(mat,k); rep(i,n){ vector> w(2,vector(1,0)); if(i