#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define int long long
const int MOD = 666013;

struct Matrix
{
    int mat[2][2];
    Matrix() {memset(mat, 0, sizeof(mat));}
    Matrix(int a00, int a01, int a10, int a11)
    {
        mat[0][0] = a00, mat[0][1] = a01;
        mat[1][0] = a10, mat[1][1] = a11;
    }
    friend Matrix operator * (const Matrix &A, const Matrix &B)
    {
        Matrix ans;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                for(int k = 0; k < 2; k++)
                    ans.mat[i][j] = (ans.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
        return ans;
    }
    static Matrix I()
    {
        return Matrix(1, 0,
                      0, 1);
    }
    Matrix putere(int exp)
    {
        Matrix ans = I(), base = *this;
        while(exp != 0)
        {
            if(exp % 2 == 1)
                ans = ans * base;
            base = base * base;
            exp /= 2;
        }
        return ans;
    }
};

signed main()
{
    int k;
    fin >> k;
    if(k == 0)
        fout << 0;
    else
    {
        Matrix A(0, 1,
                 1, 1);
        Matrix ans = A.putere(k - 1);
        fout << ans.mat[1][1] % MOD;
    }

    fin.close();
    fout.close();
    return 0;
}