#include <fstream>

using namespace std;

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

long long n,s=1,nf=1,m=9999991,i;

long long lgpow (long long b,long long p) {
  long long x,r;
  for (x=b,r=1;p>0;p>>=1) {
    if ((p & 1) !=0)
        r=r*x % m;
    x=x*x%m;
  }
  return r%m;
}

int main () {
    f >> n;
    for (i=2;i<=n;i++) {
        s=(s+lgpow(i,i-2))%m;
    }
    g << s << '\n';
    f.close();g.close();
    return 0;
}