#include #ifdef __LOCAL #define DBG(X) cout << #X << " = " << (X) << endl; #define SAY(X) cout << (X) << endl; #else #define DBG(X) #define SAY(X) #define NDEBUG #endif using namespace std; typedef int_fast32_t int32; typedef int_fast64_t int64; const int32 inf = 1e9+7; const int32 MOD = 1000000007; const int64 llinf = 1e18; #define YES(n) cout << ((n) ? "YES\n" : "NO\n" ) #define Yes(n) cout << ((n) ? "Yes\n" : "No\n" ) #define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n" ) #define ANS(n) cout << (n) << "\n" #define REP(i,n) for(int64 i=0;i<(n);++i) #define FOR(i,a,b) for(int64 i=(a);i<(b);i++) #define FORR(i,a,b) for(int64 i=(a);i>=(b);i--) #define all(obj) (obj).begin(),(obj).end() #define rall(obj) (obj).rbegin(),(obj).rend() #define fi first #define se second #define pb(a) push_back(a) typedef pair pii; typedef pair pll; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template struct ModInt{ int_fast64_t x; constexpr ModInt(int_fast64_t y = 0):x((y%mod+mod)%mod){} constexpr ModInt& operator+=(const ModInt& a){ if((x += a.x) >= mod) x -= mod; return *this; } constexpr ModInt& operator-=(const ModInt& a){ if((x -= a.x) < 0)x += mod; return *this; } constexpr ModInt& operator*=(const ModInt& a){ x = x * a.x % mod; return *this; } constexpr ModInt& operator/=(const ModInt& a){ *this *= a.inv(); return *this; } constexpr ModInt operator-() const { return ModInt(-x); } constexpr ModInt operator+(const ModInt& a) const { return ModInt(*this) += a; } constexpr ModInt operator-(const ModInt& a) const { return ModInt(*this) -= a; } constexpr ModInt operator*(const ModInt& a) const { return ModInt(*this) *= a; } constexpr ModInt operator/(const ModInt& a) const { return ModInt(*this) /= a; } constexpr ModInt operator++(){ *this += ModInt(1); return *this; } constexpr ModInt operator++(int){ ModInt old = *this; ++*this; return old; } constexpr ModInt operator--(){ *this -= ModInt(1); return *this; } constexpr ModInt operator--(int){ ModInt old = *this; --*this; return old; } constexpr bool operator==(const ModInt& a) const { return x == a.x; } constexpr bool operator!=(const ModInt& a) const { return x != a.x; } constexpr ModInt pow(int_fast64_t r) const { if(!r)return 1; ModInt res = pow(r>>1); res *= res; if(r & 1) res *= *this; return res; } constexpr ModInt inv() const { return pow(mod-2); } friend istream& operator>>(istream& is, ModInt& a){ int_fast64_t t; is >> t; a = ModInt(t); return is; } friend ostream& operator<<(ostream& os, const ModInt& a){ return os << a.x; } }; using mint = ModInt; /** * @brief Partition Table(分割数テーブル) * @docs docs/partition-table.md */ template< typename T > vector< vector< T > > partition_table(int n, int k) { vector< vector< T > > dp(n + 1, vector< T >(k + 1)); dp[0][0] = 1; for(int i = 0; i <= n; i++) { for(int j = 1; j <= k; j++) { if(i - j >= 0) dp[i][j] = dp[i][j - 1] + dp[i - j][j]; else dp[i][j] = dp[i][j - 1]; } } return dp; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int32 n; cin >> n; auto pt = partition_table(n,n); mint ans = 0; FOR(k,1,n+1){ if(n-3*k < 0)break; ans += pt[n-3*k][k]; } ANS(ans); return 0; }