#include<iostream>
#include<string>

using namespace std;

#define NM 5
#define MOD 666013
#define D 2
#define LL long long

int K;

void multiply(int A[NM][NM],int B[NM][NM],int C[NM][NM])
{
    int ans[NM][NM];   
       
    for(int i=1;i<=D;++i)
       for(int j=1;j<=D;++j)
       {
          ans[i][j]=0; 
          for(int k=1;k<=D;++k)   
          {
             ans[i][j]+=((LL)A[i][k]*B[k][j])%MOD;
             if(ans[i][j]>=MOD) ans[i][j]-=MOD;
          }   
       }   
    
    for(int i=1;i<=D;++i)
       for(int j=1;j<=D;++j)
          C[i][j]=ans[i][j];       
             
}

int main()
{
    int A[NM][NM],R[NM][NM];
    
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    
    scanf("%d",&K);
    
    memset(R,0,sizeof(R));
    
    for(int i=1;i<=D;++i)
       R[i][i]=1;
    
    A[1][1]=0;
    A[1][2]=1;
    A[2][1]=1;
    A[2][2]=1;
    
    for(int i=0;i<=29 && K;++i)  
    {
        if((1<<i)&K) 
        {
           multiply(A,R,R);
           K-=(1<<i);
        }   
        multiply(A,A,A);    
    }
    
    printf("%d",R[1][2]);
    
    return 0;
}