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