/** * date : 2020-12-24 00:44:47 */ #define NDEBUG // #include using namespace std; constexpr int MOD = 1000000007; template int naive_optimized(int MAX) { mint eight = 8; mint a[8] = {1, 1, 1, 1, 1, 1, 1, 1}; mint b[8] = {1, 2, 3, 4, 5, 6, 7, 8}; int i = 0; for (; i + 8 <= MAX; i += 8) { a[0] *= b[0]; b[0] += eight; a[1] *= b[1]; b[1] += eight; a[2] *= b[2]; b[2] += eight; a[3] *= b[3]; b[3] += eight; a[4] *= b[4]; b[4] += eight; a[5] *= b[5]; b[5] += eight; a[6] *= b[6]; b[6] += eight; a[7] *= b[7]; b[7] += eight; } mint ret = 1; for (int j = 0; j < 8; j++) ret *= a[j]; while (++i <= MAX) ret *= i; return ret.get(); } template struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(r * mod == 1, "invalid, r * mod != 1"); static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; } constexpr mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint &b) const { return mint(*this) += b; } constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } constexpr bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } constexpr mint inverse() const { return pow(mod - 2); } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = LazyMontgomeryModInt(t); return (is); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static constexpr u32 get_mod() { return mod; } }; using mint = LazyMontgomeryModInt<1000000007>; int main() { // N点M辺無向グラフのx:EGF y:OGF // G(x, y) = \sum_i (\sum_j (i(i-1)/2, j) y^j) x^i / i! // 無向連結グラフ // F(x, y) = f_{ij} x^i y^j / i! // 関係は? // 連結成分0個 1 // 連結成分1個 F // 連結成分2個 g_ij = \sum_{k,l} (i, k) f_kl f_(i-k)(j-l) / 2! // -> F^2 / 2な気がする // -> 神を信じると F(x, y) = log G(x, y) // F(x, -1) = log (\sum_{i,j} (i(i-1)/2, j) (-1)^j x^i / i!) // = log \sum_i (\sum_j (i(i-1)/2, j) (^1)^j) x^i / i!) // = log (1 + x) // = x - x^2 / 2 + x^3 / 3 ... // EGFに直すと? // (-1)^(N-1) (N-1)! が答え? // // 階乗 O(\sqrt n log n)を持っておらず、猛省… long long n = 0; char c; while (cin >> c) { n = n * 10 + c - '0'; if (n > 1e10) { cout << 0 << endl; return 0; } } if (n > (long long)mint::get_mod()) { cout << 0 << endl; return 0; } mint fac = naive_optimized(n - 1); if (n % 2 == 0) fac = -fac; cout << fac.get() << endl; }