#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const int MOD =666013;
int n ,ans , p;
int X[2][2],A[2][2];
void init()
{
    A[0][0] = A[0][1]= A[1][0] = 1;
    A[1][1] = 0;
    X[0][0] = 1;
    X[1][0] = 0;
}
void mult(int A[2][2], int B[2][2])
{
    int rez[2][2];
    memset(rez, 0 ,sizeof(rez));
    for( int i = 0 ;i < 2 ;i ++)
        for( int j =0 ;j < 2; j++)
            for(int k = 0 ;k <2 ;k ++)
            {
                rez[i][j] = (rez[i][j] + 1LL * A[i][k] *B[k][j]) % MOD;
            }
    memcpy(A, rez, sizeof(rez));
}
int  power(int A[2][2] , int p)
{
    int ans[2][2];
    ans[0][0] = ans[1][1] = 1;
    ans[0][1] = ans[1][0] = 0;
    while(p)
    {
        if( p % 2)
           mult(ans, A);
        mult(A,A);
        p/= 2;
    }
    memcpy(A , ans , sizeof(ans));
}
int main() {
    cin >> n;
    init();
    power(A, n - 1);
    mult(A, X);
    cout << A[0][0];
    return 0;
}