#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template static void amin(T &x, U y) { if (y < x) x = y; } template static void amax(T &x, U y) { if (x < y) x = y; } template struct ModInt { static const int Mod = MOD; unsigned x; ModInt() : x(0) {} ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; } ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; } int get() const { return (int)x; } ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { signed a = x, b = MOD, u = 1, v = 0; while (b) { signed t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } if (u < 0) u += Mod; ModInt res; res.x = (unsigned)u; return res; } bool operator==(ModInt that) const { return x == that.x; } bool operator!=(ModInt that) const { return x != that.x; } ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; } }; typedef ModInt<1000000007> mint; #pragma region for precomputing int berlekampMassey(const vector &s, vector &C) { int N = (int)s.size(); C.assign(N + 1, mint()); vector B(N + 1, mint()); C[0] = B[0] = 1; int degB = 0; vector T; int L = 0, m = 1; mint b = 1; for (int n = 0; n < N; ++ n) { mint d = s[n]; for (int i = 1; i <= L; ++ i) d += C[i] * s[n - i]; if (d == mint()) { ++ m; } else { if (2 * L <= n) T.assign(C.begin(), C.begin() + (L + 1)); mint coeff = -d * b.inverse(); for (int i = 0; i <= degB; ++ i) C[m + i] += coeff * B[i]; if (2 * L <= n) { L = n + 1 - L; B.swap(T); degB = (int)B.size() - 1; b = d; m = 1; } else { ++ m; } } } C.resize(L + 1); return L; } void computeMinimumPolynomialForLinearlyRecurrentSequence(const vector &a, vector &phi) { int n2 = (int)a.size(), n = n2 / 2; assert(n2 % 2 == 0); int L = berlekampMassey(a, phi); reverse(phi.begin(), phi.begin() + (L + 1)); } template int mintToSigned(ModInt a) { int x = a.get(); if (x <= MOD / 2) return x; else return x - MOD; } int outputPrecomputedMinimalPolynomial(vector seq, ostream &os) { if (seq.size() % 2 == 1) seq.pop_back(); vector phi; computeMinimumPolynomialForLinearlyRecurrentSequence(seq, phi); if (phi.size() >= seq.size() / 2 - 2) { cerr << "warning: maybe not enough terms" << endl; } cerr << "/*" << phi.size() - 1 << "*/"; os << "{{ "; rep(i, phi.size() - 1) { if (i != 0) os << ", "; os << seq[i].get(); } os << " }, { "; rep(i, phi.size()) { if (i != 0) os << ", "; os << mintToSigned(phi[i]); } os << " }}"; return (int)phi.size() - 1; } #pragma endregion int main() { //A_{i-1} - (i - 1) < A_i //A_{i-1} - i < A_i //A_N - N < A_1 //A_N <= A_1 //A_{N-1} - {N-1} < A_N //A_{N-1} < A_N + N int N; while (~scanf("%d", &N)) { mint ans; rep(ANis1, 2) { vector> dp(N - 1, vector(N + 2)); if (ANis1) { dp[0][1] += 1; } else { rer(AN, 2, N) dp[0][AN] += 1; } rep(i, N - 2) { rer(j, 1, N) { mint x = dp[i][j]; if (x.x == 0) continue; if (i + 1 <= j) { dp[i + 1][j - i] += x; dp[i + 1][N + 1 - i] -= x; } else { //k = 1 + i dp[i + 1][1] += x * (i + 1 - j); dp[i + 1][2] -= x * (i + 1 - j); dp[i + 1][1] += x; dp[i + 1][N + 1 - i] -= x; } } rer(j, 1, N) dp[i + 1][j + 1] += dp[i + 1][j]; } mint sum; rer(j, 1, N) { mint x = dp[N - 2][j]; if (x.x == 0) continue; sum += x * (N - j); if (!ANis1) sum += x; } ans += sum; } printf("%d\n", ans.get()); } return 0; }