#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
ll n, mod=666013;
int  I[2][2] = {{1, 0}, {0, 1}},a[2][2] = {{1, 1}, {1, 0}};
void mult(int a[2][2],int b[2][2]){
    int c[2][2];
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
        c[i][j]=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]*b[k][j])%mod;
 for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
        a[i][j]=c[i][j];
}
void put( int t){
while(t>0){
    if(t%2==0)
{
    mult(a,a);
    t/=2;
}
else{
    mult(I,a);
    t--;
}
}
}
int main()
{
    fin>>n;

put(n-1);
fout<<I[0][0];

    return 0;
}