Cod sursă (job #691814)

#include <bits/stdc++.h>
#define MOD 100003
#define ll long long
using namespace std;
ifstream fin("2sah.in");
ofstream fout("2sah.out");
ll PowNumber(ll x,int n)
{
    ll p=1;
    while(n)
    {
        if(n&1) p*=x,p%=MOD;
        x*=x;x%=MOD;
        n>>=1;
    }
    return p;
}
void ProductMatrix(ll a[3][3],ll b[3][3] )
{
    ll i,j,k,c[3][3];
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
    {
        c[i][j]=0;
        for(k=0;k<3;k++) c[i][j]+=a[i][k]*b[k][j]%MOD,c[i][j]%=MOD;
    }
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        a[i][j]=c[i][j]%MOD;
}
void PowMatrix(ll x[3][3],int n)
{
    ll p[3][3]={{1,0,0},{0,1,0},{0,0,1}};
    while(n)
    {
        if(n&1) ProductMatrix(p,x);
        ProductMatrix(x,x);
        n>>=1;
    }
    fout<<p[2][2];
}
int main()
{
    int task,n,k;
    fin>>task>>n>>k;
    if(task==1)
    {
        fout<<PowNumber(3,k-1);
    }
    else
    {
        ll x[3][3]={{0,1,0},{0,0,1},{1,1,1}};
        PowMatrix(x,k);
    }
    return 0;
}