#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;

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

void pow(int n, long long &a11, long long &a12, long long &a21, long long &a22)
{
    if(n%2==0)
    {
        long long b11=a11, b12=a12, b21=a21, b22=a22;
        pow(n/2,b11,b12,b21,b22);
        a11=(b11*b11+b12*b21)%MOD;
        a12=(b11*b12+b12*b22)%MOD;
        a21=(b21*b11+b22*b21)%MOD;
        a22=(b21*b12+b22*b22)%MOD;
    }
    else if(n!=1 && n%2==1)
    {
        long long b11=a11, b12=a12, b21=a21, b22=a22;
        long long c11, c12, c21, c22;
        pow(n-1,b11,b12,b21,b22);
        c11=(a11*b11+a12*b21)%MOD;
        c12=(a11*b12+a12*b22)%MOD;
        c21=(a21*b11+a22*b21)%MOD;
        c22=(a21*b12+a22*b22)%MOD;
        a11=c11; a12=c12; a21=c21; a22=c22;
    }
}

int main()
{
    long long n, a11=0, a12=1, a21=1, a22=1; f>>n;
    if(n==1||n==2) g<<1;
    else
    {
        pow(n-2,a11,a12,a21,a22);
        g<<(a12+a22)%MOD;
    }
    return 0;
}