#include <fstream>
using namespace std;

#define MOD 666013
#define KMAX 1000000001

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void copiere(long long A[][2] , long long B[][2])
{
    for(int i = 0 ; i <= 1 ; i++)
        for(int j = 0 ; j <= 1 ; j++)
            A[i][j] = B[i][j];
}

void produs(long long P[][2] , long long A[][2] , long long B[][2])
{
    P[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    P[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    P[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    P[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
}

int fibo(int n)
{
    long long A[2][2] = {{1 , 1} , {1 , 0}} , P[2][2] = {{1 , 0} , {0 , 1}} , B[2][2];
    while(n > 0)
    {
        if(n % 2 == 1)
        {
            produs(B , A , P);
            copiere(P , B);
        }
        produs(B , A , A);
        copiere(A , B);
        n /= 2;
    }
    return P[0][1];
}
int main()
{
    int n;
    fin >> n;
    fout << fibo(n);
    return 0;
}