Cod sursă (job #140322)

#include <iostream>
#include <cstdio>
#define MOD 100003
using namespace std;

int VARIANTA; long long N,k;

int main()
{
    freopen("2sah.in", "r", stdin);
    freopen("2sah.out", "w", stdout);

    scanf("%d",&VARIANTA);
    scanf("%lld%lld",&N,&k);

    if(VARIANTA==1) // calculam  3^(k-1) prin exponentiere logaritmica
    {
        long long answer=1,pow=3;

        k--;

        while(k)
        {
            if(k&1) // k%2==1
                answer=(answer*pow)%MOD;

            pow=pow*pow%MOD;

            k>>=1; // k=k/2;
        }

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

    }
    else
    {
        if(k==N) printf("1");
        else
            if(k==N-1) printf("2");
        else
            if(k==N-2) printf("4");

        else
        {
            long long a=1,b=2,c=4,x=N-3;

            long long d;

            while(x>=k)
            {
                d=(a+b+c)%MOD;
                a=b; b=c; c=d;
                x--;
            }

            printf("%lld",d);
        }
    }


    return 0;
}