#include using namespace std; typedef long long ll; #define REP(i,n) for(int i=0;i> N; if(N == 1) { printf("1\n"); } sum[1] = 1; sum[0] = 0; a[1] = 1; for(int i = 2; i <= N; ++i) { a[i] = i * sum[i - 1]; a[i] %= MOD; sum[i] = sum[i - 2] + a[i]; sum[i] %= MOD; //printf("a[%d]: %lld\n", i, a[i]); //printf("sum[%d]: %lld\n", i, sum[i]); } printf("%lld\n", a[N]); return 0; }