#include <fstream>
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int a[3][3],b[3][3],c[3][3];
void ridic(int i)
{
    if(i==2)
    {
        a[1][1]=(c[1][1]*c[1][1]%mod+c[1][2]*c[2][1]%mod)%mod;
        a[1][2]=(c[1][1]*c[1][2]%mod+c[1][2]*c[2][2]%mod)%mod;
        a[2][1]=(c[1][1]*c[2][1]%mod+c[2][1]*c[2][2]%mod)%mod;
        a[2][2]=(c[1][2]*c[2][1]%mod+c[2][2]*c[2][2]%mod)%mod;
        c[1][1]=a[1][1];
        c[1][2]=a[1][2];
        c[2][1]=a[2][1];
        c[2][2]=a[2][2];
        return ;
    }
    if(i%2==0)
    {
        ridic(i/2);
        ridic(2);
        return ;
    }
    ridic(i-1);
    a[1][1]=(c[1][1]*b[1][1]%mod+c[1][2]*b[2][1]%mod)%mod;
    a[1][2]=(c[1][1]*b[1][2]%mod+c[1][2]*b[2][2]%mod)%mod;
    a[2][1]=(b[1][1]*c[2][1]%mod+b[2][1]*c[2][2]%mod)%mod;
    a[2][2]=(b[1][2]*c[2][1]%mod+c[2][2]*b[2][2]%mod)%mod;
    c[1][1]=a[1][1];
    c[1][2]=a[1][2];
    c[2][1]=a[2][1];
    c[2][2]=a[2][2];
    return ;
}
int main()
{
    int n;
    b[1][1]=0;b[1][2]=1;b[2][1]=1;b[2][2]=1;
    c[1][1]=0;c[1][2]=1;c[2][1]=1;c[2][2]=1;
    fin>>n;
    ridic(n);
    fout<<c[2][1];
    return 0;
}