#include <bits/stdc++.h>
#define M 666013
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int a[200][2][2],b[2][2];
void inm(int n,int x,int y,int z)
{
    int i,j,k;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            for(k=0;k<n;k++)
                b[i][j]=(b[i][j]*1LL+1LL*a[x][i][k]*a[y][k][j])%M;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            a[z][i][j]=b[i][j],b[i][j]=0;
}
int put(int n,int p,int q)
{
    if(!p)
        return 0;
    if(p==1)
        return q;
    if(p%2)
    {
        inm(n,q,q,q+1);
        inm(n,q,put(n,p/2,q+1),q);
    }
    else
    {
        inm(n,q,q,q);
        put(n,p/2,q);
    }
    return q;
}
int main()
{
    int n,p,i,j;
    in>>p;
    for(i=0;i<2;i++)
        a[0][i][i]=a[1][i][1-i]=1;
    a[1][1][1]=1;
    put(2,p-1,1);
    out<<a[1][1][1];
    return 0;
}