#include <iostream>
#include <fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int mod=666013;
void inmultire(long long a[3][3], long long  b[3][3], long long c[3][3])
{
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
    {
        c[i][j]=0;
        for(int k=1; k<=2; k++)
            c[i][j]=(c[i][j]%mod + a[i][k]*b[k][j]%mod)%mod;
    }
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            a[i][j]=c[i][j];

}
int fibo(int n, long long ans[3][3])
{
    if(n<=1)
        return n;
    return ans[2][2];

}
int main()
{
    int n;
    long long c[3][3], rez[3][3];
    long long ans[3][3];
    ans[1][1]=1;
    ans[2][2]=1;
    ans[1][2]=0;
    ans[2][1]=0;

    in>>n;
    c[1][1]=0;
    c[1][2]=1;
    c[2][1]=1;
    c[2][2]=1;

    // calculez c la puterea n-1
    int p=n-1;
    while(p)
    {
        if(p%2==1)
        {
            inmultire(ans,c,rez);
        }
        inmultire(c,c,rez);
        p=p/2;
    }
    out<<fibo(n,ans);




    return 0;
}