#include <fstream>
#define m 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
void atribuire(long long a[2][2],long long b[2][2])
{
    int i,j;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)a[i][j]=b[i][j];
}
void inmultire(long long a[2][2],long long c[2][2])
{
        long long b[2][2];
        b[0][0]=(a[0][0]*c[0][0]%m+a[0][1]*c[1][0]%m)%m;
        b[0][1]=(a[0][0]*c[0][1]%m+a[0][1]*c[1][1]%m)%m;
        b[1][0]=(a[1][0]*c[0][0]%m+a[1][1]*c[1][0]%m)%m;
        b[1][1]=(a[1][0]*c[0][1]%m+a[1][1]*c[1][1]%m)%m;
        atribuire(a,b);
}
int main()
{
    int i,p;
    long long a[2][2]={0,1,1,1};
    cin>>p;
    if(p==0)cout<<0;
    else if(p==1||p==2)cout<<1;
    else
    {
        p=p-2;
        long long rez[2][2]={1,0,0,1};
        long long fib[2][2]={1,1,0,0};
        for(i=0;(1<<i)<=p;i++)
        {
            if((1<<i)&p)inmultire(rez,a);

            inmultire(a,a);
        }
        inmultire(fib,rez);
        cout<<fib[0][1];

    }
    return 0;
}