#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,2147483648};

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=0;


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;
	
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++]=(int)(log10(pt[i])/log10(2));

	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;ptm[i]!=-1;++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;
	int C;
	int i=1;
	long long val;

	int l,j,k;

	/*

	for(l=0;l<=31;l++)
	{
		for(j=0;j<2;j++)
		{
			for(k=0;k<2;k++)
			{
				printf("%u ",A[l].a[j][k]);
			}
			printf("\n");
		}
		printf("....\n");
	}*/



	C=1;//scanf("%d",&C);

	while(i<=C)
	{
		a=2234567;//scanf("%u",&a);
		b=1234568;//scanf("%u",&b);
		n=1345678918;//scanf("%u",&n);
		m=1145678918;//scanf("%u",&m);

		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++;
	}




}