#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;

ll n;
int mat[3][3],ans[3];

void create(){
                f>>n;
                ans[1]=1;
                ans[2]=1;
                mat[1][1]=1;
                mat[1][2]=1;
                mat[2][1]=1;
                mat[2][2]=0;
             }

void prodmat(int a[3][3],int b[3][3]){
                                    int c[3][3];
                                    for(int i=1;i<=2;++i)
                                       for(int j=1;j<=2;++j){
                                                              c[i][j]=0;
                                                              for(int k=1;k<=2;++k)
                                                              c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
                                                            }

                                    for(int i=1;i<=2;++i)
                                       for(int j=1;j<=2;++j)a[i][j]=c[i][j];

                                 }

void powermat(int a[3][3],ll n){
                                    int b[3][3];
                                    for(int i=1;i<=2;++i)
                                       for(int j=1;j<=2;++j)b[i][j]=(i==j);
                                    while(n){
                                              if(n%2)prodmat(b,a);
                                              prodmat(a,a);
                                              n/=2;
                                            }
                                    for(int i=1;i<=2;++i)
                                        for(int j=1;j<=2;++j)a[i][j]=b[i][j];
                               }

void ProdMatVct(int a[3],int b[3][3]){
                                          int c[3];
                                          for(int i=1;i<=2;++i){
                                                                 c[i]=0;
                                                                 for(int j=1;j<=2;++j)
                                                                 c[i]=(c[i]+1LL*a[j]*b[j][i])%MOD;
                                                               }
                                          for(int i=1;i<=2;++i)a[i]=c[i];
                                     }

int main(){
            create();
            powermat(mat,n-1);
            ProdMatVct(ans,mat);
            g<<ans[2];
            return 0;
          }