ull c,D=1<<28,x=0,A=0,T[]={1,864357307,373979365,183143523};{while(c=getchar(),'0'<=c&&c<='9'&&x<=MD)x=x*10+c-'0';x=min(x-1,MD);A=T[x/D];rep(i,x++/D*D+1,x)A=(MD-A)*i%MD;wt(A);}