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