#include <fstream>
#define mod 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
struct matrix
{
    long long a[3][3];
}baza,prod;
matrix p(matrix aa,matrix bb)
{
    matrix rez;
    for(long long i=1;i<=2;++i)
    for(long long j=1;j<=2;++j)
    {
        rez.a[i][j]=0;
        for(long long k=1;k<=2;++k)
            rez.a[i][j]=(rez.a[i][j]+(aa.a[i][k]*bb.a[k][j])%mod)%mod;
    }
    return rez;
}
matrix power(matrix baza,long long exp)
{
    if(exp==1)
        return baza;
    matrix x=power(baza,exp/2);
    if(exp%2==0)
        return p(x,x);
    return p(p(x,x),baza);
}
int main()
{
    long long n;
    cin>>n;
    if(n==0)
    {
        cout<<0;
        return 0;
    }
    if(n==1)
    {
        cout<<1;
        return 0;
    }
    baza.a[1][1]=0;
    baza.a[1][2]=baza.a[2][1]=baza.a[2][2]=1;
    prod=power(baza,n-1);
    cout<<prod.a[2][2];
    return 0;
}