Cod sursă (job #178300)

# include <cstdio>
# define MOD 100003
# define tip long long
using namespace std;
FILE *f=freopen("2sah.in","r",stdin),*g=freopen("2sah.out","w",stdout);
tip A[3][3],S[3][3],C[3][3];
void sol1(tip),sol2(tip,tip);
int main()
{
	tip n,k,t;
	scanf("%lld%lld%lld",&t,&n,&k);
	if(t==1)sol1(k);
	else sol2(n,k);
}
void sol1(tip k)
{
	tip r=1,n=3;
	for(--k;k;k>>=1)
		{if(k&1)r=(r*n)%MOD;
		n=(n*n)%MOD;}
	printf("%lld",r);
}
void sol2(tip n,tip k)
{
	tip j,i,q;
	k=n+1-k;
	for(i=0;i<3;++i)
	{
		S[i][i]=1;
		A[2][i]=1;
	}
	A[1][2]=A[0][1]=1;
	for(;k;k>>=1)
	{
		if(k%2)
		{
			for(i=0;i<3;++i)
				for(j=0;j<3;++j)
				{
					C[i][j]=0;
					for(q=0;q<3;++q)
						C[i][j]=(C[i][j]+S[i][q]*A[q][j])%MOD;
				}
			for(i=0;i<3;i++)
				for(j=0;j<3;++j)
					S[i][j]=C[i][j];
		}
		for(i=0;i<3;++i)
			for(j=0;j<3;++j)
			{
				C[i][j]=0;
				for(q=0;q<3;q++)
					C[i][j]=(C[i][j]+A[i][q]*A[q][j])%MOD;
			}
		for(i=0;i<3;++i)
			for(j=0;j<3;++j)
				A[i][j]=C[i][j];
	}
	printf("%lld",((S[0][0]+S[0][1])%MOD+2*S[0][2])%MOD);
}