#include <bits/stdc++.h>

#define VMAX 100000
#define NMAX 7500
#define LOG 17

#define INF (long long)(1e9)
#define MOD 666013
#define BASE 23

#define ll  long long int


using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

int I2[2][2] = {{1,0} , {0,1}};

void cpy(int a[2][2],int b[2][2])
{
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            a[i][j] = b[i][j];
        }
    }
}
void mult(int a[2][2],int b[2][2])
{
    int c[2][2] = {0};
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                c[i][j] += a[i][k] * 1ll *  b[k][j] % MOD;
                c[i][j] %= MOD;
            }
        }
    }
    cpy(a,c);
}
void pwr(int a[2][2] , int b)
{
    if(!b)
    {
        cpy(a,I2);
        return;
    }
    int c[2][2];
    cpy(c,a);
    pwr(c,b/2);
    mult(c,c);
    if(b%2)
    {
        mult(c,a);
    }
    cpy(a,c);

}
int main()
{


    int n;
    fin >> n;
    int a[2][2] = {{1,1} , {1,0}};
    if(n==0 || n==1)
    {
        fout << n;
        return 0;
    }
    pwr(a,n-1);
    fout << a[0][0];

}