#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define ll long long
#define N  1000000
#define mod 666013 //1000000007
ll n;
ll b[5][5],a[5][5],c[5][5];
int main()
{
    fin>>n;
    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    b[1][1]=1;
    b[1][2]=0;
    b[2][1]=0;
    b[2][2]=1;
    n--;
    while(n)
    {
        if(n%2==1)
        {
            for(int i=1; i<=2; i++)
                for(int j=1; j<=2; j++)
                    for(int t=1; t<=2; t++)
                        c[i][j]=(c[i][j]+(a[i][t]*b[t][j])%mod)%mod;
            for(int i=1; i<=2; i++)
                for(int j=1; j<=2; j++)
                {
                    b[i][j]=c[i][j];
                    c[i][j]=0;
                }

        }
        for(int i=1; i<=2; i++)
            for(int j=1; j<=2; j++)
                for(int t=1; t<=2; t++)
                    c[i][j]=(c[i][j]+(a[i][t]*a[t][j])%mod)%mod;
        for(int i=1; i<=2; i++)
            for(int j=1; j<=2; j++)
            {
                a[i][j]=c[i][j];
                c[i][j]=0;
            }
        n/=2;
    }
    fout<<(b[2][2]%mod)%mod<<"\n";
}