#include <bits/stdc++.h>

using namespace std;

int sol[3][3],m[3][3],c[3][3],init[3][3];
const int mod=666013;
void multmat(int a[][3],int b[][3])
{
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            c[i][j]=(1LL*a[i][1]*b[1][j]+1LL*a[i][2]*b[2][j])%mod;
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            a[i][j]=c[i][j];
}
void rpl(int k)
{
    sol[1][1]=1;
    sol[1][2]=0;
    sol[2][1]=0;
    sol[2][2]=1;
    while(k)
    {
        if(k%2==1)
        {
            multmat(sol,m);
            k--;
        }
        else
        {
            multmat(m,m);
            k/=2;
        }
    }
}
int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int k;
    cin>>k;
    m[1][1]=-1;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            m[i][j]++;
    init[1][1]=0;
    init[1][2]=1;
    rpl(k-1);
    multmat(init,sol);
    cout<<init[1][2];
    return 0;
}