#include <cstdio>

#define Mod 9999991
#define NMax 1000005

using namespace std;

long long N, DP[NMax];

int main()
{
    freopen ("dirichlet.in", "r", stdin);
    freopen ("dirichlet.out", "w", stdout);
    scanf ("%d", &N);
    int Two=2;
    DP[0]=1;
    for (int i=1; i<=N; ++i, Two*=2, Two%=Mod)
    {
        DP[i]=i+Two-1;
        DP[i]%=Mod;
    }
    printf ("%d\n", DP[N-1]);
    return 0;
}