Cod sursă (job #691792)

#include <bits/stdc++.h>
#include <unordered_map>
#include <map>

using namespace std;

ifstream fin("2sah.in");
ofstream fout("2sah.out");
//-----------------------------------------
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
//-----------------------------------------
#define f(i,s,e) for(int i=s;i<=e;++i)
#define nf(i,s,e) for(i=s;i<e;++i)
#define rf(i,e,s) for(i=e;i>=s;--i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sp <<" "
//------------------------------------------
const int NMAX = 1e2 + 20;
const int KMAX = 1e1 + 5;
const int MOD = 1e5 + 3;
const int INF = 0x3f3f3f3f;
//------------------------------------------
int task, n, k;
ll m1[15][15], m2[15][15];
//------------------------------------------
void read() {
    fin >> task >> n >> k;
}
int powlog(int x, int y) {
    long long rez = 1;
    while (y) {
        if (y & 1)
            rez = 1LL * rez * x % MOD;
        x = 1LL * x * x % MOD;
        y /= 2;
    }
    return rez;
}
void mult(long long a[][15], long long b[][15]) {
    int c[5][5];
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            c[i][j] = 0;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++)
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            a[i][j] = c[i][j];
}
void op(int x) {
    while (x) {
        if (x & 1)
            mult(m1, m2);
        mult(m2, m2);
        x /= 2;
    }
}
void solve() {
    if (task == 1) {
        fout << powlog(3, k - 1);
        return;
    }
    else {
        m1[1][2] = m1[1][3] = 1;
        for (int i = 1; i <= 3; ++i)
            m2[i][3] = 1;
        m2[2][1] = 1;
        m2[3][2] = 1;
        op(n-k);
        fout << m1[1][3];
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    read();
    solve();
    return 0;
}