// Σ[k=1..N]{ C(N,k) * k^(N-k) }
combination_mint c;
ll N;
mint x;
{
	c.init(1d5+1);
	rd(N);
	rep(i,1,N+1)x+=c.C(N,i)*((mint)i).pw(N-i);
	wt(x);
}