#pragma GCC optimize("O3") #include using namespace std; using ll=long long; using P=pair; template using V=vector; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); constexpr ll mod=1000000007; ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;} ll lcm(ll c,ll d){return c/gcd(c,d)*d;} struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout< bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } struct mint{ using ull=unsigned long long int; ull v; mint(ll vv=0){s(vv%mod+mod);} mint& s(ull vv){ v=vv>=1; } return res; } mint inv()const{return pow(mod-2);} //拡張ユークリッドの互除法 /* mint inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return mint(x); }*/ friend ostream& operator<<(ostream&os,const mint&val){ return os<(const mint&val)const{return v>val.v;} }; ll n;//n項前のフィボナッチ数列 O(n^3 log k) vector matmul(vector &dp,vector> &mat){ vector res(n,0); for(int i=0;i> update(vector> &mat){ vector> res(n,vector(n,0)); for(int i=0;i &dp,vector> &mat,ll k){ while(k){ if(k&1)dp=matmul(dp,mat); mat=update(mat); k>>=1; } } int main(){ n=2; ll N,m,k,p,q; cin>>N>>m>>k>>p>>q; V b(N); for(int i=0;i>b[i]; mint A,B; B=mint(p)/mint(q); A=mint(1)-B; vector dp1(2,1),dp2(2,1); dp1[1]=0;dp2[0]=0; vector> mat1(2,vector(2)),mat2(2,vector(2)); mat1[0][0]=mat1[1][1]=A; mat1[0][1]=mat1[1][0]=B; mat2[0][0]=mat2[1][1]=A; mat2[0][1]=mat2[1][0]=B; matpow(dp1,mat1,k); matpow(dp2,mat2,k); mint ans=0; for(int i=0;i