#include <fstream>
#define mod 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
typedef long long ll;
struct matrix
{
    ll v[3][3];
}a,f,nul;
matrix prod(matrix a,matrix b)
{
    matrix c=nul;
    for(ll i=1;i<=2;++i)
    for(ll j=1;j<=2;++j)
    for(ll k=1;k<=2;++k)
        c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;
    return c;
}
matrix power(matrix a,ll b)
{
    if(b==1)
        return a;
    matrix x=power(a,b/2);
    if(b%2==0) return prod(x,x);
    return prod(a,prod(x,x));
}
int main()
{
    ll k; cin>>k;
    if(k<=2)
    {
        if(k==0) cout<<0;
        else if(k==1) cout<<1;
        else cout<<1;
        return 0;
    }
    a.v[1][1]=0; a.v[1][2]=a.v[2][1]=a.v[2][2]=1;
    nul.v[1][1]=nul.v[1][2]=nul.v[2][1]=nul.v[2][2]=0;
    f=power(a,k-1);
    cout<<f.v[2][2];
    return 0;
}