Untitled

#include<stdio.h>
#include <math.h>


long long m;

int st[2][2]={1,1,1,0};

long long final[2][2];

long long pt[32]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,
					16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648ll};

long long ptm[32]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int indeks;


struct TAB
{
	long long a[2][2];
}A[32];


wypelnij_tab()
{
	int i=1;

	A[0].a[0][0]=1;
	A[0].a[0][1]=1;
	A[0].a[1][0]=1;
	A[0].a[1][1]=0;
	
	while(i<=31)
	{
		A[i].a[0][0] = A[i-1].a[0][0]*A[i-1].a[0][0] + A[i-1].a[0][1]*A[i-1].a[1][0];
		if(A[i].a[0][0]>=m)A[i].a[0][0]=A[i].a[0][0]%m;
		A[i].a[0][1] = A[i-1].a[0][0]*A[i-1].a[0][1] + A[i-1].a[0][1]*A[i-1].a[1][1];
		if(A[i].a[0][1]>=m) A[i].a[0][1]=A[i].a[0][1]%m;
		A[i].a[1][0] = A[i-1].a[1][0]*A[i-1].a[0][0] + A[i-1].a[1][1]*A[i-1].a[1][0];
		if(A[i].a[1][0]>=m) A[i].a[1][0]=A[i].a[1][0]%m;
		A[i].a[1][1] = A[i-1].a[1][0]*A[i-1].a[0][1] + A[i-1].a[1][1]*A[i-1].a[1][1];
		if(A[i].a[1][1]>=m)A[i].a[1][1]=A[i].a[1][1]%m;
		
		i++;
	}

}

poteguj(long long n)
{
	int i;
	indeks=0;	
do
{

	for(i=0;;++i)
	{
		if(pt[i]>=n)
			break;
	}
	if(pt[i]!=n)
		i--; //maksymalna potega czyli dla 20 bedzie to 16 
		
	ptm[indeks++]=(long long)(log10(pt[i])/log10(2) + 0.5);
	
	n=n-pt[i];	

}while(n!=0);


}

mnoz_maciez_st()
{
	int i;
	long long a,c;

	final[0][0]=A[ptm[0]].a[0][0];
	if(final[0][0]>=m) final[0][0]=final[0][0]%m;
	
	final[0][1]=A[ptm[0]].a[0][1];
	if(final[0][1]>=m) final[0][1]=final[0][1]%m;
	
	final[1][0]=A[ptm[0]].a[1][0];
	if(final[1][0]>=m) final[1][0]=final[1][0]%m;
	
	final[1][1]=A[ptm[0]].a[1][1];
	if(final[1][1]>=m) final[1][1]=final[1][1]%m;

	a=final[0][0];
	c=final[1][0];

	for(i=1;i<indeks;++i)
	{
		final[0][0]=a*A[ptm[i]].a[0][0] + final[0][1]*A[ptm[i]].a[1][0];
			if(final[0][0]>=m) final[0][0]=final[0][0]%m;

		final[0][1]=a*A[ptm[i]].a[0][1] + final[0][1]*A[ptm[i]].a[1][1];
			if(final[0][1]>=m) final[0][1]=final[0][1]%m;

		final[1][0]=c*A[ptm[i]].a[0][0] + final[1][1]*A[ptm[i]].a[1][0];
			if(final[1][0]>=m) final[1][0]=final[1][0]%m;

		final[1][1]=c*A[ptm[i]].a[0][1] + final[1][1]*A[ptm[i]].a[1][1];
			if(final[1][1]>=m) final[1][1]=final[1][1]%m;

		a=final[0][0];
		c=final[1][0];
	}

}


main()
{
	long long a,b,n;
	unsigned int b1,n1,a1,m1;
	int C;
	int i=1;
	long long val;

	scanf("%d",&C);

	while(i<=C)
	{

		scanf("%u",&a1);
		scanf("%u",&b1);
		scanf("%u",&n1);
		scanf("%u",&m1);
		
		a=(long long)(a1);
        b=(long long)(b1);
        n=(long long)(n1);
		m=(long long)(m1);
/*
a= 1234567;
b= 1234567;
n= 1345678910;
m= 1345678910;

a= 2234567;
b= 1234568;
n= 1345678918;
m= 1145678918;

a= 1345678910;
b= 1345678910;
n= 1345678918;
m= 1145678917;*/

		if(n==0)
		{
                val=(a%m+b%m)%m;
        }
        else
        {
           wypelnij_tab();

		   poteguj(n);

	    	mnoz_maciez_st();

	     	val=(a+b)*final[0][0]+b*final[1][0];
	      	val=val%m;
        }

		printf("%lld\n",val);

		i++;
	}
}