Cod sursă (job #432257)

#include <fstream>

using namespace std;

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

long long a[3][3] = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}, mat[1][3] = {2, 1, 1};

inline void inmult(int n, long long A[][3], long long B[][3])
{
    int rez[n][3];
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 3; ++j)
            rez[i][j] = 0;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            for (int k = 0; k < 3; ++k)
                rez[i][j] = (rez[i][j] + (A[i][k] * B[k][j]) % 100003) % 100003;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 3; ++j)
            A[i][j] = rez[i][j];
    }
}

inline int lgput(int a, int p)
{
    int sol = 1;
    while (p)
    {
        if (p % 2 == 1)
            sol = (sol * a) % 100003;
        a = ((a % 100003) * (a % 100003)) % 100003;
        p /= 2;
    }
    return sol % 100003;
}

inline void put(int n)
{
    while (n)
    {
        if (n & 1)
            inmult(1, mat, a);
        inmult(3, a, a);
        n >>= 1;
    }
}

int main()
{
    int t;
    long long n, k;
    in >> t >> n >> k;
    if (t == 1)
        out << lgput(3, k - 1);
    else
    {
        k = n + 1 - k;
        if (k < 0)
            out << 0;
        else if (k <= 2)
            out << mat[0][2 - k];
        else
        {
            put(k - 2);
            out << mat[0][0];
        }
    }
    return 0;
}