#include #define REP(i,n,N) for(ll i=(n);i<(ll) N;i++) #define RREP(i,n,N) for(int i=N-1;i>=(int) n;i--) #define p(s) cout<<(s)<>N; ll gu=2,ki=1; ll tg=0,tk=0; for(ll i=3;i<=N;i++){ if(i%2==0) { tg=gu; gu+=i*ki; gu%=inf; } else { tk=ki; ki+=i*gu; ki%=inf; } } p(N%2?(ki-tk+inf)%inf:(gu-tg+inf)%inf); return 0; }