#include <fstream>
#define int long long
#define MOD 666013

using namespace std;

int sol[2][2]={1, 0, 0, 1};
int c[2][2]={0, 1, 1, 1};
int a[2][2]={1, 1, 0, 0};

void multiply(int a0[2][2], int b0[2][2])
{
    int c[2][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]+=a0[i][k]*b0[k][j];
                c[i][j]%=MOD;
            }
        }
    }
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            a0[i][j]=c[i][j];
        }
    }
}

void pow(int n)
{
    while(n > 0)
    {
        if(n%2 == 1)
        {
            n--;
            multiply(sol, c);
        }
        else
        {
            n/=2;
            multiply(c, c);
        }
    }
}

int32_t main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int n;
    cin>>n;
    pow(n-1);
    multiply(a, sol);
    cout<<a[0][0];
    return 0;
}