#include #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template ostream& operator<<(ostream& o,const pair &p){return o<<"("< ostream& operator<<(ostream& o,const vector &vc){o<<"sz = "< struct ModInt{ using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr static uint mod = mod_; uint v; ModInt():v(0){} ModInt(ll v):v(normS(v%mod+mod)){} explicit operator bool() const {return v!=0;} static uint normS(const uint &x){return (x [0 , mod-1] static ModInt make(const uint &x){ModInt m; m.v=x; return m;} ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));} ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));} ModInt operator-() const { return make(normS(mod-v)); } ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);} ModInt operator/(const ModInt& b) const { return *this*b.inv();} ModInt& operator+=(const ModInt& b){ return *this=*this+b;} ModInt& operator-=(const ModInt& b){ return *this=*this-b;} ModInt& operator*=(const ModInt& b){ return *this=*this*b;} ModInt& operator/=(const ModInt& b){ return *this=*this/b;} ll extgcd(ll a,ll b,ll &x,ll &y) const{ ll u[]={a,1,0},v[]={b,0,1}; while(*v){ ll t=*u/ *v; rep(i,3) swap(u[i]-=t*v[i],v[i]); } if(u[0]<0) rep(i,3) u[i]=-u[i]; x=u[1],y=u[2]; return u[0]; } ModInt inv() const{ ll x,y; extgcd(v,mod,x,y); return make(normS(x+mod)); } bool operator==(const ModInt& b) const { return v==b.v;} bool operator!=(const ModInt& b) const { return v!=b.v;} friend istream& operator>>(istream &o,ModInt& x){ ll tmp; o>>tmp; x=ModInt(tmp); return o; } friend ostream& operator<<(ostream &o,const ModInt& x){ return o<; int N; int main(){ cin>>N; mint ans = 0; { vector dp(N,1); rep(t,N-1){ vector adp(N+1,0); rep(i,N) adp[i+1] = adp[i]+dp[i]; vector ndp(N,0); int d = max(1,t); rep(x,N) ndp[x] = adp[min(N,x+d)]; dp = ndp; } rep(i,N) ans += dp[i]; } { vector dp(N,0); dp[0]=1; rep(t,N-1){ vector adp(N+1,0); rep(i,N) adp[i+1] = adp[i]+dp[i]; vector ndp(N,0); int d = max(1,t); rep(x,N) ndp[x] = adp[min(N,x+d)]; dp = ndp; } ans -= dp[N-1]; } cout<