#include <cstdio>
#define Mod 9999991

using namespace std;

int a[2][2],b[2][2],n;

inline void inm(int a[2][2],int b[2][2])
{
    int c[2][2];
    c[0][0]=(int)((1LL*a[0][0]*b[0][0]+ 1LL*a[0][1]*b[1][0])%Mod);
    c[0][1]=(int)((1LL*a[0][0]*b[0][1]+ 1LL*a[0][1]*b[1][1])%Mod);
    c[1][0]=(int)((1LL*a[1][0]*b[0][0]+ 1LL*a[1][1]*b[1][0])%Mod);
    c[1][1]=(int)((1LL*a[1][0]*b[0][1]+ 1LL*a[1][1]*b[1][1])%Mod);

    a[0][0]=c[0][0];
    a[0][1]=c[0][1];
    a[1][1]=c[1][1];
    a[1][0]=c[1][0];
}

inline void putere(int x)
{
    if(!x) return;
    if(x&1) inm(a,a);
    inm(b,a);
    putere(x>>1);
}

int main()
{
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);

    scanf("%d",&n);
    a[0][0]=0;a[0][1]=a[1][0]=a[1][1]=1;
    b[0][0]=b[1][1]=1;

    putere(n);
    printf("%d\n",b[0][0]);

    return 0;
}