#include <fstream>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int n;
int a[2][2]={0,1,1,1};
int ans[2][2]={1,0,0,1};
void prod(int b[2][2],int c[2][2],int ok)
{
    int d[2][2];
    d[0][0]=((1LL*b[0][0]*c[0][0]%MOD)+(1LL*b[0][1]*c[1][0]%MOD))%MOD;
    d[0][1]=((1LL*b[0][0]*c[1][0]%MOD)+(1LL*b[0][1]*c[1][1]%MOD))%MOD;
    d[1][0]=((1LL*b[1][0]*c[0][0]%MOD)+(1LL*b[1][1]*c[1][0]%MOD))%MOD;
    d[1][1]=((1LL*b[1][0]*c[1][0]%MOD)+(1LL*b[1][1]*c[1][1]%MOD))%MOD;
    if(ok)
        ans[0][0]=d[0][0],ans[1][0]=d[1][0],ans[1][1]=d[1][1],ans[0][1]=d[0][1];
    else
        a[0][0]=d[0][0],a[1][0]=d[1][0],a[1][1]=d[1][1],a[0][1]=d[0][1];
}
int main()
{
    f>>n;
    while(n)
    {
        if(n%2==1)
        {
            prod(ans,a,1);
        }
        prod(a,a,0);
        n/=2;
    }
    g<<ans[0][1];
    return 0;
}