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

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

struct matrice
{
    int m[3][3];
};

int n;

matrice inmultesc ( matrice a, matrice b )
{
    matrice ans;

    for ( int i = 1; i <= 3 ; i++ )
        for ( int j = 1; j <= 3; j++ )
            ans.m[i][j] = 0;

    for ( int i = 1; i <= 3; i++ )
        for ( int j = 1; j <= 3; j++ )
            for ( int k =1; k <= 3; k++ )
                ans.m[i][j] = ( ans.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;

    return ans;

}

int main()
{
    fin >> n;

    matrice a,b,ans;

    a.m[1][1] = a.m[1][2] = a.m[2][1] = 1;
    a.m[2][2] = 0;

    b.m[1][1] = b.m[2][1] = 1;
    b.m[1][2] = b.m[2][2] = 0;

    while ( n >= 1 )
    {
        if( n % 2 == 1 )
            ans = inmultesc ( ans, a );

        a = inmultesc ( a, a );
        n /= 2;
    }

    ans = inmultesc (ans,b);

    fout << ans.m[1][1];
}