#include <fstream>
#include <cstring>
#define int64 long long
#define mod 666013
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int z[3][3],f[3][3];
int64 n;
void mult(int a[3][3],int b[3][3],int c[3][3])
{
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
    for(int k=1;k<=2;k++)
        c[i][j]=(c[i][j]+a[i][k]*1LL*b[k][j])%mod;
}
int fib(int64 p)
{
    z[1][2]=z[2][1]=z[2][2]=1;
    int c[3][3];
    memcpy(f,z,sizeof(z));
    while(p>0)
    {
        if(p%2)
        {
            memset(c,0,sizeof(c));
            mult(z,f,c);
            memcpy(f,c,sizeof(c));
            p--;
        }
        memset(c,0,sizeof(c));
        mult(z,z,c);
        memcpy(z,c,sizeof(c));
        p/=2;
    }
    return f[1][2]%mod;
}
int main()
{
    in>>n;
    out<<fib(n-1)<<'\n';
    return 0;
}