#include<fstream> 
#include<cstdlib> 
using namespace std; 
ifstream f("kfib.in"); 
ofstream g("kfib.out"); 
long long a,b,A[3][3],r[3][3],c1[3][3],c2[3][3]; 
int main () 
{ 
    int b=666013;
	f>>a; 
    A[1][1]=c1[1][1]=0; 
    A[1][2]=c1[1][2]=1; 
    A[2][1]=c1[2][1]=1; 
    A[2][2]=c1[2][2]=1; 
    r[1][1]=c2[1][1]=1; 
    r[1][2]=c2[1][2]=0; 
    r[2][1]=c2[2][1]=0; 
    r[2][2]=c2[2][2]=1; 
    while(a) 
        { 
            if(a%2==0) 
                { 
                    A[1][1]=(c1[1][1]*c1[1][1]+c1[1][2]*c1[2][1])%b; 
                    A[1][2]=(c1[1][1]*c1[1][2]+c1[1][2]*c1[2][2])%b; 
                    A[2][1]=(c1[2][1]*c1[1][1]+c1[2][2]*c1[2][1])%b; 
                    A[2][2]=(c1[2][1]*c1[1][2]+c1[2][2]*c1[2][2])%b; 
                    c1[1][1]=A[1][1]; 
                    c1[1][2]=A[1][2]; 
                    c1[2][1]=A[2][1]; 
                    c1[2][2]=A[2][2]; 
                    a=a/2; 
                } 
                else 
                { 
                    r[1][1]=(c2[1][1]*c1[1][1]+c2[1][2]*c1[2][1])%b; 
                    r[1][2]=(c2[1][1]*c1[1][2]+c2[1][2]*c1[2][2])%b; 
                    r[2][1]=(c2[2][1]*c1[1][1]+c2[2][2]*c1[2][1])%b; 
                    r[2][2]=(c2[2][1]*c1[1][2]+c2[2][2]*c1[2][2])%b; 
                    c2[1][1]=r[1][1]; 
                    c2[1][2]=r[1][2]; 
                    c2[2][1]=r[2][1]; 
                    c2[2][2]=r[2][2]; 
                    A[1][1]=(c1[1][1]*c1[1][1]+c1[1][2]*c1[2][1])%b; 
                    A[1][2]=(c1[1][1]*c1[1][2]+c1[1][2]*c1[2][2])%b; 
                    A[2][1]=(c1[2][1]*c1[1][1]+c1[2][2]*c1[2][1])%b; 
                    A[2][2]=(c1[2][1]*c1[1][2]+c1[2][2]*c1[2][2])%b; 
                    c1[1][1]=A[1][1]; 
                    c1[1][2]=A[1][2]; 
                    c1[2][1]=A[2][1]; 
                    c1[2][2]=A[2][2]; 
                    a=(a-1)/2; 
                } 
        } 
    g<<r[1][2]<<'\n'; 
    f.close(); 
    g.close(); 
    return 0; 
}