#include <fstream>
#define mod 666013
#define int long long
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
int n,sol[2][2],aux[2][2];
void inmult(int a[][2],int b[][2])
{
    int aux[2][2];
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            aux[i][j]=0;
            for(int k=0;k<2;k++)
            {
                aux[i][j]=(aux[i][j]+a[i][k]*b[k][j])%mod;
            }
        }
    }
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            a[i][j]=aux[i][j];
        }
    }
}
signed main()
{
    cin>>n;
    if(n<2) cout<<n;
    else
    {
        n-=1;
        long long sol[2][2]={ {1,0},{0,1} };
        long long aux[2][2]={ {0,1},{1,1} };
        while(n!=0)
        {
            if(n%2==1) inmult(sol,aux);
            n/=2;
            inmult(aux,aux);
        }
        cout<<sol[1][1];
    }
    return 0;
}