#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

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

int n, A[2][2], C[2][2], S[2][2];


int main()
{
    in>>n;
    A[0][0] = A[1][0] = A[0][1] = 1;
    S[0][0] = S[1][0] = S[0][1] = 1;

    for(n-=2; n>0; n>>=1){

        if(n % 2)
        {
            for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                {
                    C[i][j] = 0;
                    for(int k = 0; k<2; k++)
                        C[i][j] = (C[i][j] + 1LL*S[i][k]*A[k][j]) %MOD;
                }
            for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                    S[i][j] = C[i][j];
        }
        for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                {
                    C[i][j] = 0;
                    for(int k = 0; k<2; k++)
                        C[i][j] = (C[i][j]+ 1LL*A[i][k]*A[k][j]) % MOD;
                }

        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
                A[i][j] = C[i][j];


    }

    out<<S[0][0];

    return 0;
}