#ifdef KOMAKI_LOCAL #include #else #define NDEBUG #endif #include #include #include using namespace std; #define i64 int64_t #define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i) #define sz(v) ((i64)((v).size())) #define bit(n) (((i64)1)<<((i64)(n))) #define all(v) (v).begin(), (v).end() /******************************************************************/ /* */ /* Undefine "GF_USE_FIXED_GF" to use various mods, but slower. */ /* To use fixed one, set your mod at "static const int mod = ;" */ /* */ /******************************************************************/ #define GF_USE_FIXED_GF template class GF { public: #ifdef GF_USE_FIXED_GF static const T mod = 1e9 + 7; // Set your mod! GF() { permutation_memo = std::vector(1, 1); inverse_memo = std::vector(2, 1); permutation_inverse_memo = std::vector(2, 1); } #else T mod; GF(T mod) : mod(mod) { permutation_memo = std::vector(1, 1); inverse_memo = std::vector(2, 1); permutation_inverse_memo = std::vector(2, 1); } #endif T norm(T i); T add(T i0, T i1); T sub(T i0, T i1); T mul(T i0, T i1); T div(T i0, T i1); T pow(T i, int64_t p); T inv(T i); T permInv(T i); T permutation(T n, T m); // n * (n - 1) * ... * (n - m + 1), Non limited memorization, Avoid segmentation fault! T combination(T n, T m); // Memorized for n < MEMO_SIZE_LIMIT. private: static const int MEMO_SIZE_LIMIT = 2000000; std::vector permutation_memo; std::vector inverse_memo; std::vector permutation_inverse_memo; }; template inline T GF::permutation(T n, T m) { if(m < 0 || n < m) return 0; while(permutation_memo.size() <= n){ permutation_memo.push_back(mul(permutation_memo.back(), permutation_memo.size())); } return mul(permutation_memo[n], permInv(n - m)); } template inline T GF::combination(T n, T m) { if(m < 0 || n < m) return 0; if(n - m < m) m = n - m; if(n < MEMO_SIZE_LIMIT){ T num = permutation(n, n); T den = mul(permInv(m), permInv(n - m)); return mul(num, den); } T num = 1, den = 1; for(T i = 0; i < m; ++i){ num = mul(num, n - i); den = mul(den, i + 1); } return div(num, den); } template inline T GF::norm(T i) { return (i % mod + mod) % mod; } template inline T GF::add(T i0, T i1) { T res = i0 + i1; if(mod <= res) return res - mod; return res; } template inline T GF::sub(T i0, T i1) { T res = i0 - i1; if(res < 0) return res + mod; return res; } template inline T GF::mul(T i0, T i1) { return (int64_t)i0 * i1 % mod; } template inline T GF::div(T i0, T i1) { return mul(i0, inv(i1)); } template inline T GF::permInv(T i) { while(permutation_inverse_memo.size() <= i){ permutation_inverse_memo.push_back(mul(permutation_inverse_memo.back(), inv(permutation_inverse_memo.size()))); } return permutation_inverse_memo[i]; } template inline T GF::inv(T i) { if(i < MEMO_SIZE_LIMIT){ while(inverse_memo.size() <= i){ // Deformation of formula. // b[t] * t = (M - (M / t) * t) * b[M - (M / t) * t]; // Divides by i over a finite field GF(mod), b[t] = - (M / t) * b[M % t]. int size = inverse_memo.size(); inverse_memo.push_back(mod - (int64_t)(mod / size) * inverse_memo[mod % size] % mod); } return inverse_memo[i]; } return this->pow(i, mod - 2); } template inline T GF::pow(T i, int64_t p) { T res = 1; for(; p; p >>= 1){ if(p & 1) res = mul(res, i); i = mul(i, i); } return res; } const i64 N = 1005; const i64 MOD = 1e9 + 7; i64 dp[N][N]; i64 sub_dp[N][N]; i64 recur(i64 pos, i64 rem); i64 subRecur(i64 pos, i64 rem) { if(pos < 0) return 0; if(rem == 0) return 1; if(pos == 0) return 0; i64 &res = sub_dp[pos][rem]; if(res != -1) return res; return res = (recur(pos, rem) + subRecur(pos - 1, rem - 1)) % MOD; } i64 recur(i64 pos, i64 rem) { if(pos < 0) return 0; if(rem == 0) return 1; if(pos == 0) return 0; i64 &res = dp[pos][rem]; if(res != -1) return res; res = recur(pos - 1, rem - 0); res = (res + subRecur(pos - 2, rem - 1) * 2) % MOD; return res; } int main() { memset(dp, -1, sizeof(dp)); memset(sub_dp, -1, sizeof(sub_dp)); i64 n; cin >> n; i64 ans = 0; GF gf; rep(i, n){ i64 k = gf.permutation(n - i, n - i); i64 way = 0; for(i64 use = 0; use <= i; ++use) way = way + recur(n / 2, use) * recur(n - n / 2, i - use) % MOD; ans += k * way % MOD * (i % 2 == 0 ? 1 : -1); } cout << (ans % MOD + MOD) % MOD << endl; }