#line 1 "a.cpp" #include #include using namespace std; #line 1 "/home/kotatsugame/library/math/matrix.cpp" #include #include template struct Matrix{ vector >dat; int N,M;//N x M matrix Matrix(){} Matrix(int N_):Matrix(N_,N_){} Matrix(int N_,int M_):N(N_),M(M_),dat(N_,vector(M_)){} vector&operator[](int i){return dat[i];} const vector&operator[](int i)const{return dat[i];} static Matrix eye(int N) { Matrix res(N); for(int i=0;i>=1)if(n&1)res=res*a; return res; } template Matrix operator+(const U&A)const { Matrix res(N,M); for(int i=0;i Matrix operator-(const U&A)const { Matrix res(N,M); for(int i=0;i Matrix operator*(const U&A)const { Matrix res(N,M); for(int i=0;i; mint pA,pB; int S,T; int K; main() { { int m,n; cin>>m>>n; pA=m; pA/=n; } cin>>S; { int m,n; cin>>m>>n; pB=m; pB/=n; } cin>>T>>K; int W=S+T+1; mat A(2*W); for(int i=0;i0;j--) { A[j][W+i]=p*(1-pB); p*=pB; } A[W][W+i]=p; } mat E(2*W,1); E[T][0]=1; A=A.pow(K*2)*E; cout<