So Easy!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3849 Accepted Submission(s): 1266

Problem Description

　　A sequence S

_n is defined as:

Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate S

_n.

　　You, a top coder, say: So easy!

Input

　　There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 2

¹⁵, (a-1)

²< b < a

², 0 < b, n < 2

³¹.The input will finish with the end of file.

Output

　　For each the case, output an integer S

_n.

Sample Input

2 3 1 20132 3 2 20132 2 1 2013

Sample Output

Source

Recommend

zhoujiaqi2010 | We have carefully selected several similar problems for you:

/*告诉你a,b,n,m,求0
    
     <2^15 , (a-1)^2
     
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;struct matrix{	ll mat[2][2];};matrix mul(matrix &a,matrix &b,ll mm){	matrix c;	for(int i=0;i<2;i++)	{		for(int j=0;j<2;j++)		{			c.mat[i][j]=0;			for(int k=0;k<2;k++)			{				c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]);			}			c.mat[i][j]%=mm;		}	}	return c;}matrix inti(){	matrix ans;	for(int i=0;i<2;i++)	{		for(int j=0;j<2;j++)		ans.mat[i][j]=(i==j);	}	return ans;}matrix ks(matrix a,ll k,ll mm){	matrix ans=inti();	while(k)	{		if(k&1)		ans=mul(ans,a,mm);		a=mul(a,a,mm);		k>>=1;	}	return ans;}int main(){	matrix M;	ll a,b,n;	ll m;	while(~scanf("%lld%lld%lld%lld",&a,&b,&n,&m))	{		M.mat[0][0]=a;		M.mat[1][1]=a;		M.mat[0][1]=b;		M.mat[1][0]=1;		matrix ans=ks(M,n,m);		ll x=ans.mat[0][0];		cout<<(2*x)%m<