#include #include using namespace std; using T=atcoder::modint; struct matrix{ int h,w; vector> val; matrix(int r,int c=-1):h(r),w(c){ if (w==-1) w=h; val.assign(h,vector(w,0)); } matrix operator*(matrix b){ matrix a=*this,c(h,w); for (int i=0;i0){ if (k%2==1) ret=ret*m; m=m*m; k/=2; } return ret; } }; int main(){ int n=2; vector> tmp(n,vector(2)); matrix m(n); for (int i=0;i>tmp[i][j]; int s,t; cin>>s>>t; long long N,K; cin>>N>>K; T::set_mod(K); for (int i=0;i