Cod sursă (job #757808)

#include <bits/stdc++.h>
using namespace std;

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

const int MOD = 100003;

class Matrix {
    int n;
    vector<vector<int>> mat;

public:
    Matrix(int n) : n(n), mat(n, vector<int>(n)) { }
    vector<int>& operator[](int ind) { return mat[ind]; }

    static Matrix null(int n) {
        Matrix ret(n);
        for (int i = 0; i < n; i++)
            ret[i][i] = 1;
        return ret;
    }

    friend Matrix operator*(Matrix x, Matrix y);
    friend vector<int> operator*(Matrix x, vector<int> y);
    friend Matrix pwr(Matrix x, int y);
};

Matrix operator*(Matrix x, Matrix y) {
    Matrix ret(x.n);
    for (int i = 0; i < x.n; i++)
        for (int j = 0; j < x.n; j++)
            for (int k = 0; k < x.n; k++)
                ret[i][j] = (ret[i][j] + 1LL * x[i][k] * y[k][j]) % MOD;
    return ret;
}

vector<int> operator*(Matrix x, vector<int> y) {
    vector<int> ret(x.n);
    for (int i = 0; i < x.n; i++)
        for (int k = 0; k < x.n; k++)
            ret[i] = (ret[i] + 1LL * x[i][k] * y[k]) % MOD;
    return ret;
}

Matrix pwr(Matrix x, int y) {
    if (!y)
        return Matrix::null(x.n);
    if (y % 2)
        return x * pwr(x * x, y / 2);
    return pwr(x * x, y / 2);
}

int pwr(int x, int n) {
    if (!n)
        return 1;
    if (n % 2)
        return 1LL * x * pwr(1LL * x * x % MOD, n / 2) % MOD;
    return pwr(1LL * x * x % MOD, n / 2);
}

int main() {
    int t, n, k; fin >> t >> n >> k;
    if (t == 1)
        fout << pwr(3, k - 1) << '\n';
    else if (n - k == 0)
        fout << "1\n";
    else if (n - k == 1)
        fout << "2\n";
    else {
        vector<int> vec = {1, 2, 4};
        Matrix mat(3);
        mat[0][0] = 0; mat[0][1] = 1; mat[0][2] = 0;
        mat[1][0] = 0; mat[1][1] = 0; mat[1][2] = 1;
        mat[2][0] = 1; mat[2][1] = 1; mat[2][2] = 1;
        fout << (pwr(mat, n - k - 2) * vec)[2] << '\n';
    }
    return 0;
}