#include <iostream>
#include <fstream>
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

#define MOD 666013

int N;

class Mat
{
public:
    int A[2][2];
    Mat () {
        A[0][0] = A[0][1] = A[1][0] = A[1][1] = 0;
    }
    Mat (const Mat& other) {
        A[0][0] = other.A[0][0];
        A[0][1] = other.A[0][1];
        A[1][0] = other.A[1][0];
        A[1][1] = other.A[1][1];
    }
    Mat operator * (const Mat& other)
    {
        Mat aux;
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                for(int k=0;k<=1;k++)
                    aux.A[i][j] += (1LL * A[i][k] * other.A[k][j]) % MOD;
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                aux.A[i][j] %= MOD;
        return aux;
    }
};

inline Mat lgPut(Mat N, int P)
{
    Mat power(N), Sol;
    Sol.A[0][0] = Sol.A[1][1] = 1;
    while(P)
    {
        if(P&1)
            Sol = Sol * power; 
        P >>= 1;
        power = power * power; 
    }
    return Sol;
}

int main()
{
    f >> N;
    Mat A; A.A[0][1] = A.A[1][0] = A.A[1][1] = 1;
    if(N == 0)
        g << 0;
    else if(N == 1)
        g << 1;
    else
    {
        Mat Sol = lgPut(A, N-1);
        g << Sol.A[1][1];
    }
}