#include <bits/stdc++.h> typedef long long ll; using namespace std; const ll mod = 1e9+7; struct matrix { ll a[3][3]; matrix operator * (matrix b) { matrix ans; for(int i=0;i<3;++i) for(int j=0;j<3;++j) ans.a[i][j] = 0; for(int i=0;i<3;++i) for(int j=0;j<3;++j) { for(int k=0;k<3;++k) ans.a[i][j] += (a[i][k]*b.a[k][j])%(mod-1); ans.a[i][j] %= mod-1; } return ans; } void operator = (matrix b) { for(int i=0;i<3;++i) for(int j=0;j<3;++j) a[i][j] = b.a[i][j]; } }; void matrixPow(matrix &fib,matrix &e,ll n) { int temp = n; while(temp>1) { if(temp&1) e = fib*e; fib = fib*fib; temp >>= 1; } fib = fib*e; } ll fastPow(ll aa,ll b) { ll t = 1; while(b>1) { if(b&1) t = t*aa%mod; aa = aa*aa%mod; b >>= 1; } return aa*t%mod; } int main() { ll n,aa,b,x,y,f = 0; scanf("%lld%lld%lld%lld%lld",&n,&x,&y,&aa,&b); if(n==1) printf("%lld\n",x%mod); else if(n==2) printf("%lld\n",y%mod); else { if(aa%mod==0||x%mod==0||y%mod==0) printf("0\n"); else { matrix fib,e,p; for(int i=0;i<3;++i) for(int j=0;j<3;++j) fib.a[i][j] = e.a[i][j] = p.a[i][j] = 0; fib.a[0][1] = fib.a[1][0] = fib.a[1][1] = 1; e.a[0][0] = e.a[1][1] = 1; matrixPow(fib,e,n-3); p.a[0][0] = p.a[1][0] = 1; fib = fib*p; matrix fib2,e2; for(int i=0;i<3;++i) for(int j=0;j<3;++j) fib2.a[i][j] = e2.a[i][j] = 0; fib2.a[0][0] = fib2.a[1][2] = fib2.a[2][0] = fib2.a[2][1] = fib2.a[2][2] = 1; e2.a[0][0] = e2.a[1][1] = e2.a[2][2] = 1; p.a[2][0] = 2; x %= mod; y %= mod; aa = fastPow(aa%mod,b%(mod-1)); matrixPow(fib2,e2,n-3); fib2 = fib2*p; f = (fastPow(x,fib.a[0][0])*fastPow(y,fib.a[1][0]))%mod*fastPow(aa%mod,fib2.a[1][0]%(mod-1))%mod; //printf("%lld %lld %lld\n",fib.a[0][0],fib.a[1][0],fib2.a[1][0]); printf("%lld\n",f); } } return 0; }
全部评论
(1) 回帖