#include #include #include #include #include #include constexpr int MOD = 1e9 + 7; struct modint { int n; modint(int n = 0) : n(n) {} }; modint operator+(modint a, modint b) { return modint((a.n += b.n) >= MOD ? a.n - MOD : a.n); } modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + MOD : a.n); } modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % MOD); } modint &operator+=(modint &a, modint b) { return a = a + b; } modint &operator-=(modint &a, modint b) { return a = a - b; } modint &operator*=(modint &a, modint b) { return a = a * b; } int main() { int n; std::cin >> n; static modint dp0[2002]; static modint dp1[2002]; memset(dp0, 0, sizeof(dp0)); modint ans; // A[N]<=A[1] -> A'[1]<=A'[2] // A[1]<=A[2] -> A'[2]<=A'[3] // A[2]<=A[3]+1 -> A'[3]<=A'[4]+1 // A[3]<=A[4]+2 -> A'[4]<=A'[5]+2 // A[4]<=A[5]+3 -> A'[5]<=A'[6]+3 // ... // A[N-1]<=A[N]+N-2 -> A'[N]<=A'[1]+N-2 // A'[N]=1 { memset(dp0, 0, sizeof(dp0)); dp0[1] = 1; for (int i = 2; i <= n; i++) { memset(dp1, 0, sizeof(dp1)); for (int j = 1; j <= n; j++) { dp0[j + 1] += dp0[j]; } for (int j = 1; j <= n; j++) { dp1[j] = dp0[std::min(n, j + std::max(0, i - 3))]; } std::swap(dp0, dp1); } for (int i = 1; i <= n - 1; i++) { ans += dp0[i]; } } // A'[N]>=2 { memset(dp0, 0, sizeof(dp0)); for (int i = 2; i <= n; i++) { dp0[i] = 1; } for (int i = 2; i <= n; i++) { memset(dp1, 0, sizeof(dp1)); for (int j = 1; j <= n; j++) { dp0[j + 1] += dp0[j]; } for (int j = 1; j <= n; j++) { dp1[j] = dp0[std::min(n, j + std::max(0, i - 3))]; } std::swap(dp0, dp1); } for (int i = 1; i <= n; i++) { ans += dp0[i]; } } std::cout << ans.n << std::endl; }