#include <iostream>
#include <fstream>
using namespace std;

int main(){
    ifstream inr ("kfib.in");
    ofstream our ("kfib.out");
    int k, a=0, m=0,b=0, n=1,c=0,p=1,u=666013; 
    inr >> k;
    k-=2;
    while(k>0){
             if(!k%2){
                      k/=2;
                      a=(m*m+n*n)%u;
                      b=(m*n+n*p)%u;
                      m=a; n=b; p=(m+n)%u;
                      }
                      else{
                      k--;
                      m=n; n=p;
                      p=(m+p)%u;  
                      }
             }
    our << p;
    return 0;
    }