#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;
#include <fstream>
ifstream fi("kfib.in");
ofstream fo("kfib.out");

struct Matrix
{
    long long mat[3][3];

    Matrix(long long a, long long b, long long c, long long d)
    {
        mat[1][1] = a;
        mat[1][2] = b;
        mat[2][1] = c;
        mat[2][2] = d;
    }
};

Matrix Multiply(Matrix a, Matrix b)
{
    Matrix rez = Matrix(0, 0, 0, 0);

    for(int i = 1; i <= 2; ++i)
        for(int j = 1; j <= 2; ++j)
            for(int k = 1; k <= 2; ++k)
                rez.mat[i][j] = (rez.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;

    return rez;
}

Matrix LgPut(Matrix a, int nr)
{
    Matrix rez = Matrix(1, 0, 0, 1);
    cout << nr <<"\n";
    for(int i = 1; i <= 2; ++i)
    {
        for(int j = 1; j <= 2; ++j)
            cout <<a.mat[i][j]<<" ";
        cout << "\n";
    }

    while(nr)
    {
        if(nr % 2)
            rez = Multiply(rez, a);

        a = Multiply(a, a);
        nr /= 2;
        cout << nr <<"\n";
        for(int i = 1; i <= 2; ++i)
        {
            for(int j = 1; j <= 2; ++j)
                cout <<a.mat[i][j]<<" ";
            cout << "\n";
        }
    }

    return rez;
}

int main()
{
    Matrix fibo = Matrix(0, 1, 1, 1);
    int N;

    fi >> N;

    int sum = 0;

    fibo = LgPut(fibo, N-1);

    fo << (fibo.mat[1][1] + fibo.mat[1][2]) % MOD;
}