#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() template void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get(t); deploy(os, t); } template std::ostream& operator<<(std::ostream &os, const std::tuple &t){ os << "("; deploy<0, std::tuple, Ts...>(os, t); os << ")"; return os; } template std::ostream& operator<<(std::ostream &os, std::vector &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::set &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::queue &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::priority_queue &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::pair &p){ os << "(" << p.first << ", " << p.second << ")"; return os; } template std::ostream& operator<<(std::ostream &os, std::map &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::unordered_map &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } #define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; } #define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; } #define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; } #define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; } #define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; } #define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; } #define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; } /******************************************************************/ /* */ /* 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; } GF gf; const i64 N = 1005; const i64 MOD = 1e9 + 7; i64 dp[N][N], 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 = gf.add(recur(pos, rem), subRecur(pos - 1, rem - 1)); } 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 = 0 < pos ? recur(pos - 1, rem) : 0; res = gf.add(res, gf.mul(subRecur(pos - 2, rem - 1), 2)); return res; } int main() { memset(dp, -1, sizeof(dp)); memset(sub_dp, -1, sizeof(sub_dp)); i64 n; cin >> n; i64 ans = 0; rep(i, n){ i64 k = gf.permutation(n - i, n - i); i64 way = 0; for(i64 use = 0; use <= i; ++use) way = gf.add(way, gf.mul(recur(n / 2, use), recur(n - n / 2, i - use))); ans = gf.add(ans, gf.mul(gf.mul(k, way), gf.norm(i % 2 == 0 ? 1 : -1))); } cout << ans << endl; }