#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e5+,M=(<<)+,mod=;

int n,len,r[M],a[M],b[M],ans,jcn[N];

void upd(int &x){x>=mod?x-=mod:;x<?x+=mod:;}

int pw(int x,int k)

{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}

void ntt(int *a,bool fx)

{

  for(int i=;i<len;i++)

    if(i<r[i])swap(a[i],a[r[i]]);

  for(int R=;R<=len;R<<=)

    {

      int Wn=pw( ,fx?(mod-)-(mod-)/R:(mod-)/R );

      for(int i=,m=R>>;i<len;i+=R)

    for(int j=,w=;j<m;j++,w=(ll)w*Wn%mod)

      {

        int x=a[i+j], y=(ll)w*a[i+m+j]%mod;

        a[i+j]=x+y;  upd(a[i+j]);

        a[i+m+j]=x+mod-y;  upd(a[i+m+j]);

      }

    }

  if(!fx)return ; int inv=pw(len,mod-);

  for(int i=;i<len;i++)a[i]=(ll)a[i]*inv%mod;

}

int main()

{

  scanf("%d",&n);

  jcn[]=;for(int i=;i<=n;i++)jcn[i]=(ll)jcn[i-]*i%mod;

  jcn[n]=pw(jcn[n],mod-); for(int i=n-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

  for(int i=,fx=;i<=n;i++,fx=-fx)

    {

      a[i]=fx*jcn[i]+mod;upd(a[i]);

    }

  for(int i=;i<=n;i++)

    {

      int k=-i;

      if(!k)

    {

      b[i]=(ll)(n+)*jcn[i]%mod;

    }

      else

    {

      int d=pw(i,n+);

      if(k<)k+=mod;  k=pw(k,mod-);

      b[i]=(ll)(+mod-d)*k%mod*jcn[i]%mod;

    }

    }

  for(len=;len<=n<<;len<<=);

  for(int i=;i<len;i++)r[i]=(r[i>>]>>)+((i&)?len>>:);//len>>1!! not <<1

  ntt(a,);  ntt(b,);

  for(int i=;i<len;i++)a[i]=(ll)a[i]*b[i]%mod;

  ntt(a,);

  for(int i=,jc=,lj=;i<=n;i++,jc=(ll)jc*i%mod,lj<<=,upd(lj))

    ans=(ans+(ll)lj*jc%mod*a[i])%mod;

  printf("%d\n",ans);

  return ;

}