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