Cod sursă (job #715900)

#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>

#define ll long long

///define int ll

using namespace std;

ifstream in("2sah.in");
ofstream out("2sah.out");

const int MOD = 100003;
const int NMAX = 1005;
const char nl = '\n';

int q, n, k, sum, fib1, fib2, fib3, fib4;

ll lgput(ll n, ll p){
    ll r = 1;
    while(p){
        if(p % 2 != 0)
            r = (r * n) % MOD;
        n = (n * n) % MOD;
        p = p / 2;
    }
    return r;
}

void solve1(){
    sum = 1;
    out << lgput(3, k - 1) % MOD << nl;
}

void solve2(){
    fib2 = 1, fib3 = 1, k = n + 2 - k;
    if(k < 3)
        out << 1 << nl;
    else{
        for(int i = 3; i <= k; ++i){
            fib4 = (fib1 + fib2 + fib3) % MOD;
            fib1 = fib2, fib2 = fib3, fib3 = fib4;
        }
        out << fib4 % MOD << nl;
    }
}

int main(){
    in >> q >> n >> k;
    if(q == 1)
        solve1();
    else
        solve2();
    return 0;
}