stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

using namespace std;

long long a[100005],sum[100005];

int main(){

	int n,i;

	long long cont;

	while(cin>>n){

		cont=0;

	 for (i=0;i<n;i++)

	 cin>>a[i];

	 sort(a,a+n);

	 sum[0]=a[0];

	 for (i=1;i<n;i++)

	 sum[i]=sum[i-1]+a[i];

	 for (i=n;i>0;i--)

	 if (a[i]<=sum[i-1]*2)

	 cont++;

	 else

	 break;

	 cout<<cont<<endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

using namespace std;

main()

{

    int num;

    scanf("%d",&num);

    int animal[num];

    for (int i=0;i<num;i++)

    {

        scanf("%d",&animal[i]);

    }

    sort(animal,animal+num);

    long long sum=animal[0];

    long long cnt=1;

    for (int i=1;i<num;i++)

    {

        if (sum*2>=animal[i])

        {

            cnt++;

        }

        else

        {

            cnt=1;

        }

        sum+=animal[i];

    }

    printf("%d",cnt);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<algorithm>

#include<vector>

using namespace std;

int main()

{

    long n,k;

    scanf("%ld",&n);

    k=0;

    vector<long long> a(n);

    long long pre,sum;

    for(int i=0; i<n; i++)

    {

        scanf("%lld",&a[i]);

    }

    sort(a.begin(),a.end());

    pre=a[0];

    for(int i=1; i<n; i++)

    {

        sum=pre+a[i];

        //printf("%lld %lld %lld\n",a[i],pre,sum);

        if(2*pre<a[i]) k=i;

        pre=sum;

    }

    printf("%ld",n-k);





}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

using namespace std;

main()

{

    int num;

    scanf("%d",&num);

    int animal[num];

    for (int i=0;i<num;i++)

    {

        scanf("%d",&animal[i]);

    }

    sort(animal,animal+num);

    long long sum=animal[0];

    long long cnt=1;

    for (int i=1;i<num;i++)

    {

        if (sum*2>=animal[i])

        {

            cnt++;

        }

        else

        {

            cnt=1;

        }

        sum+=animal[i];

    }

    printf("%d",cnt);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int n, a[100001];

long long sum[100001];

int main() {

	cin >> n;

	for(int i = 1; i <= n; i++) cin >> a[i];

	sort(a+1, a+n+1);

	for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i];

	for(int i = n-1; i >= 0; i--) {

		if(a[i+1] > 2*sum[i]) {

			cout << n-i;

			return 0;

		}

	}

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

using namespace std;

main()

{

    int num;

    scanf("%d",&num);

    int animal[num];

    for (int i=0;i<num;i++)

    {

        scanf("%d",&animal[i]);

    }

    sort(animal,animal+num);

    long long sum=animal[0];

    long long cnt=1;

    for (int i=1;i<num;i++)

    {

        if (sum*2>=animal[i])

        {

            cnt++;

        }

        else

        {

            cnt=1;

        }

        sum+=animal[i];

    }

    printf("%d",cnt);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define rank tipa_rank

#define pb push_back

#define mp make_pair

#define ll long long

#define ull unsigned long long

#define INF 1000000000

#define EPS 1e-6

#define EPS2 1e-8

using namespace std;

const ll MOD = INF + 7;

using namespace std;

int ans;

int n;

int a[100000];

bool good(int x)

{

	ll sz = 0;

	for(int i = 0; i <= x; i++)

	{

		sz += a[i];

	}

	bool good = true;

	for(int i = x + 1; i < n; i++)

	{

		if(a[i] <= 2 * sz)

		{

			sz += a[i];

		}

		else

		{

			good = false;

			break;

		}

	}

	return good;

}

int main()

{

	scanf("%d" , &n);

	for(int i = 0; i < n; i++)

		scanf("%d" , &a[i]);

	sort(a , a + n);

	int l = 0 , r = n - 1;

	while(abs(r - l) > 1)

	{

		int m = (l + r) / 2;

		if(good(m))

		{

			r = m;

		}

		else

		{

			l = m + 1;

		}

	}

	if(l > r)

	{

		swap(l , r);

	}

	if(good(l))

	{

		cout << n - l;

	}

	else

		cout << n - r;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN=110000;

int n, a[MAXN];

bool check(int k)

{

	long long s=0;

	for (int i=1; i<=k; i++) s+=a[i];

	for (int i=k+1; i<=n; i++)

	{

		if (2*s<a[i]) return 0;

		s+=a[i];

	}

	return 1;

}

int main()

{

//	freopen("B.in", "r", stdin);

//	freopen("B.out", "w", stdout);

	scanf("%d", &n);

	for (int i=1; i<=n; i++) scanf("%d", &a[i]);

	sort(a+1, a+n+1);

	int l=1, r=n;

	while (l<r)

	{

		int mid=l+r>>1;

		if (check(mid)) r=mid;

		else l=mid+1;

	}

	printf("%d\n", n-l+1);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 100000 + 47;

const int MOD = 1000 * 1000 * 1000 + 7;



int A[MAX];

LL P[MAX];



int main()

{

	//freopen("in.txt", "r", stdin);

	//freopen("out.txt", "w", stdout);

	ios::sync_with_stdio(false); cin.tie(0);

	int n;

	cin >> n;

	LL s = 0;

	FOR(i, 0, n)

	{

		cin >> A[i];

	}



	sort(A, A + n);

	FOR(i, 0, n)

	{

		P[i] = A[i];

		if (i) P[i] += P[i - 1];

	}



	int ind = -1;

	RFOR(i, n - 1, 0)

	{

		if (P[i] * 2 < A[i + 1])

		{

			ind = i;

			break;

		}

	}



	cout << n - ind - 1 << endl;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN=110000;

int n, a[MAXN];

bool check(int k)

{

	long long s=0;

	for (int i=1; i<=k; i++) s+=a[i];

	for (int i=k+1; i<=n; i++)

	{

		if (2*s<a[i]) return 0;

		s+=a[i];

	}

	return 1;

}

int main()

{

//	freopen("B.in", "r", stdin);

//	freopen("B.out", "w", stdout);

	scanf("%d", &n);

	for (int i=1; i<=n; i++) scanf("%d", &a[i]);

	sort(a+1, a+n+1);

	int l=1, r=n;

	while (l<r)

	{

		int mid=l+r>>1;

		if (check(mid)) r=mid;

		else l=mid+1;

	}

	printf("%d\n", n-l+1);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <queue>

#include <stdlib.h>

#include <stack>

#include <string.h>

#include <set>

#include <iomanip>

#include <ctime>

#include <map>

#include <cmath>

#include <algorithm>

#include <sstream>

#include <cstring>

#define eps 1e-15

#define ull unsigned long long

//priority_queue<int,vector<int>,greater<int> > q;

//priority_queue<int,vector<int>,less<int> > q;

//#define ls l, mid, rt << 1

//#define rs mid + 1, r, rt << 1 | 1

using namespace std;

typedef long long ll;

//typedef pair<int,int> P;

const int inf = 0x3f3f3f3f;

const int mod = 1e9+7;

const long long mod1 = 1e16;

//int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}

//int Find(int x){return x == p[x] ? x : p[x] = Find(p[x]);}

//#define lson 1<<rt

//#define rson 1<<rt|1

const int maxn=1e5+7;

#define pi 3.1415926535898

#define PI atan(1.0)*4

int dx[4]= {0,1,0,-1},dy[4]= {1,0,-1,0};

int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};

int dir1[8][2]= {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};

//int d[]= {1,-1,4,-4}; //八数码问题

//----------------------------------------



int n,ans=1;

ll a[maxn],s;



int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++)

        a[i]+=a[i-1];

    for(int i=n-1;i;--i)

        if(a[i]*2>=a[i+1]-a[i])

            ++ans;

        else

            break;

    cout<<ans<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN=110000;

int n, a[MAXN];

bool check(int k)

{

	long long s=0;

	for (int i=1; i<=k; i++) s+=a[i];

	for (int i=k+1; i<=n; i++)

	{

		if (2*s<a[i]) return 0;

		s+=a[i];

	}

	return 1;

}

int main()

{

//	freopen("B.in", "r", stdin);

//	freopen("B.out", "w", stdout);

	scanf("%d", &n);

	for (int i=1; i<=n; i++) scanf("%d", &a[i]);

	sort(a+1, a+n+1);

	int l=1, r=n;

	while (l<r)

	{

		int mid=l+r>>1;

		if (check(mid)) r=mid;

		else l=mid+1;

	}

	printf("%d\n", n-l+1);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <stack>

#include <vector>

#define mt(a) memset(a,0,sizeof(a))

#define ll long long

const ll INF = 0x3f3f3f3f;

using namespace std;

int main (void)

{

	int n;

	ll a[100050];

	ll p[100050];

	mt(a);

	mt(p);

	cin>>n;

	for(int i=1;i<=n;i++)

		cin>>a[i],p[i] = a[i];

	sort(a+1,a+1+n);

	sort(p+1,p+1+n);

	ll x = 0;

	for(int i=1;i<=n-1;i++)

	{

		p[i]+=x;

		x = p[i];

	}

	int l = 0;

	int r = n;

	int cnt = INF;

	while(l<=r)

	{

		int mid = (l+r)/2;

		if(2*p[mid]>=a[n])

		{

			cnt = min(mid,cnt);

			r = mid-1;

		}

		else

		{

			for(int j=mid+1;j<=n-1;j++)

			{

				if(2*p[mid]>=a[j])

				{

					p[mid]+=a[j];

					if(2*p[mid]>=a[n])

						break;

				}

				else

					break;

			}

			if(2*p[mid]>=a[n])

			{

				cnt = min(mid,cnt);

				r = mid-1;

			}

			else

				l = mid+1;

		}

	}

	cout<<n-cnt+1<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<stack>

#include<queue>

#include<algorithm>

#include<iostream>

#define ll long long

using namespace std;

#define max(a,b)	(a)>(b)?(a):(b)

#define min(a,b)	(a)<(b)?(a):(b)

#define s(i)		scanf("%d",&(i))

#define ss(i)		scanf("%s",(i))

#define p(i)		printf("%d",i)

#define ps(i)		printf("%s",(i))

#define pc(i)		printf("%c",(i))

#define end			printf("\n")

#define f(i,n)		for(i=1;i<=n;i++)

#define w(i)		while(i--)

int a[100010]; 

ll b[100010];

int main()

{

	int n,m,i,j;

	s(n);

	f(i,n)

		s(a[i]);

	sort(a+1,a+n+1);

	f(i,n)

		b[i]=b[i-1]+a[i];

	for(i=n-1;i>=1;i--)

	{

		if(b[i]*2<a[i+1])

			break;

	}

	p(n-i);

	end;

	return 0; 

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <string>

#include <vector>

#include <math.h>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#define PI 3.14159265359

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pai;

typedef pair<ll, ll> pal;

const int MOD = 1e9+7;

const ll LLINF = 1e18;



ll modpow(ll a, ll n){

	ll res = 1;

	while(n > 0){

		if (n & 1) res = res * a %MOD;

		a = a * a % MOD;

		n >>= 1;

	}

	return res;

}



ll dp[801][2001];



int main(){

	int s;

	cin >> s;



	for (int i = 3; i <= s; i++){

		dp[1][i] = 1;

	}

	for (int i = 1; i < 800; i++){

		for (int j = 0; j <= s; j++){

			if (dp[i][j] != 0){

				for (int k = 3; j+k <= s; k++){

					dp[i+1][j+k] += dp[i][j];

					dp[i+1][j+k] %= MOD;

				}

			}

		}

	}

	ll ans = 0; 

	for (int i = 1; i < 800; i++){

		ans += dp[i][s];

		ans %= MOD;

	}

	cout << ans << endl;

	return 0;

}




// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <string>

#include <vector>

#include <math.h>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#define PI 3.14159265359

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pai;

typedef pair<ll, ll> pal;

const int MOD = 1e9+7;

const ll LLINF = 1e18;



int dp[2001];

int main(){

	int s;

	cin >> s;

	dp[3] = 1;

	for (int i = 4; i <= s; i++){

		dp[i] = dp[i-1] + dp[i-3];

		dp[i] %= MOD;

	}

	cout << dp[s] << endl;

	return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <stdio.h>

#include <iostream>

#include <algorithm>

#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

const int MOD=1e9+7;

const int MAXN=1e2;

typedef long long ll;

int dp[2010];

int main()

{

    ios;

    int s;

    cin>>s;

    dp[0]=1;

    for(int i=0;i<=s;i++){

        for(int j=3;i+j<=s;j++){

            dp[i+j]=(dp[i+j]+dp[i])%MOD;

        }

    }

    cout<<dp[s]<<'\n';

    return 0;

}

// Optimized solution to the same problem (faster):
#include<algorithm>

#include<string>

#include<math.h>



using namespace std;



typedef long long ll;



const ll mod = 1e9+7;



ll x[2010];

int S;



int main(){

	x[1]=x[2]=0,x[3]=x[4]=x[5]=1;

	for(int i=6;i<2010;i++){

		x[i]=(x[i-1]+x[i-3])%mod;

	}

	scanf("%d",&S);

	printf("%d",x[S]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

//#include <atcoder/all>

//using namespace atcoder;

using ll = long long;

#define pp pair<int,int>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

#define ld long double

#define al(a) (a).begin(),(a).end()

#define mk make_pair

#define check cout<<"?"<<endl;



template<typename T>

ostream& operator<<(ostream& os,const vector<T>& v){

    if(v.empty()){

        os<<"{ }";

        return os;

    }

    os<<"{"<<v.front();

    for(auto itr=++v.begin();itr!=v.end();itr++){

        os<<", "<<*itr;

    }

    os<<"}";

    return os;

}



ll MOD=1000000007;

ll mod=998244353;

int inf=1000001000;

ll INF=1e18+5;



vector<ll> inv,fac;



void inverse(ll n){

    //要素数:n+1 (0~n)

    inv[0]=1;

    inv[1]=1;

    for(ll i=2;i<=n;i++){

        inv[i]=(MOD-inv[MOD%i]*(MOD/i))%MOD;

    }

}



void inverse_u(ll n){

    //要素数:n+1 (0~n)

    for(ll i=2;i<=n;i++){

        inv[i]=(inv[i]*inv[i-1])%MOD;

    }

}



void factorial(ll n){

    //要素数:n+1 (0~n)

    fac[0]=1;

    fac[1]=1;

    for(ll i=2;i<=n;i++){

        fac[i]=(fac[i-1]*i)%MOD;

    }

}



ll nCr(ll n,ll r){

    return fac[n]*inv[r]%MOD*inv[n-r]%MOD;

}



ll proinverse(ll x,ll m){

    ll res=1,M=m-2;

    while(M>0){

        if(M&1) res=res*x%m;

        x=x*x%m;

        M>>=1;

    }

    return res;

}



void init_nCr(ll n){

    inv.assign(n+1,0);

    fac.assign(n+1,0);

    inverse(n); inverse_u(n);

    factorial(n);

}



int main(){

    ll s; cin>>s;

    init_nCr(10000);

    ll ans=0;

    for(ll i=1;i*3<=s;i++){

        ans=ans+nCr(i-1+s-3*i,i-1);

        ans%=MOD;

    }

    cout<<(MOD+ans)%MOD<<endl;

}

// Optimized solution to the same problem (faster):
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

//#include <atcoder/all>

//using namespace atcoder;

using ll = long long;

#define pp pair<int,int>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

#define ld long double

#define al(a) (a).begin(),(a).end()

#define mk make_pair

#define check cout<<"?"<<endl;



template<typename T>

ostream& operator<<(ostream& os,const vector<T>& v){

    if(v.empty()){

        os<<"{ }";

        return os;

    }

    os<<"{"<<v.front();

    for(auto itr=++v.begin();itr!=v.end();itr++){

        os<<", "<<*itr;

    }

    os<<"}";

    return os;

}



ll MOD=1000000007;

ll mod=998244353;

int inf=1000001000;

ll INF=1e18+5;



int main(){

    ll s,sum=0; cin>>s;

    if(s<3){

        cout<<0<<endl;

        return 0;

    }

    vector<ll> dp(s+1,0);

    dp[3]=0;

    for(int i=3;i<=s;i++){

        dp[i]=(dp[i]+sum+1)%MOD;

        sum=(sum+dp[i-2])%MOD;

    }

    cout<<dp[s]<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <vector>

#include <algorithm>

#include <stdio.h>

using namespace std;

using ll = long long;

using ld = long double;

#define INF 1000000000000

#define fr first

#define sc second

using vl =vector<ll>;

using vvl =vector<vl>;

const ll md = 1000000007;

vl fac(2,1), ifac(2,1);



ll ad(ll a, ll b, ll mod = md) {

    return (a%mod + b%mod + mod) % mod;

}



ll ml(ll a, ll b, ll mod = md) {

    return ( (a%mod) * (b%mod) ) % mod;

}



ll pw(ll x, ll n, ll mod = md) {

    ll res = 1;

    x %= mod;

    while (n) {

        if (n & 1)  res = (res*x)%mod;

        n = (n >> 1);

        x = (x*x)%mod;

    }

    return res;

}



void cachefact(ll lim, ll mod = md) {

    for(int i = 2; i <= lim; i++) {

        ifac.push_back((ifac[mod%i] * (mod - mod/i) % mod)%mod);

    }

    for(ll i = 2; i <= lim; i++) {

        fac.push_back((fac[i-1] * i)%mod);

        ifac[i] = (ifac[i-1] * ifac[i])%mod;

    }

}



ll C(ll n, ll r, ll mod = md) {

    if(n < r) return 0;

    return ml(fac[n], ml(ifac[r], ifac[n-r], mod), mod);

}



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cachefact(1e4);

    ll s;

    cin >> s;

    ll ans = 0;

    for(int i = 1; i <= s/3; ++i) {

    	// a1 + a2 + a3 + ... ai = s-i*3

    	ans += C(s-2*i-1, i-1);

    	ans %= md;

    }

    cout << ans << "\n";

    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cmath>

#include <vector>

#include <algorithm>

#include <stdio.h>

using namespace std;

using ll = long long;

using ld = long double;

#define INF 1000000000000

#define fr first

#define sc second

using vl =vector<ll>;

using vvl =vector<vl>;

const ll md = 1000000007;



ll ad(ll a, ll b, ll mod = md) {

    return (a%mod + b%mod + mod) % mod;

}



ll ml(ll a, ll b, ll mod = md) {

    return ( (a%mod) * (b%mod) ) % mod;

}



void multiply(vvl &F, vvl &R, ll N) {

	vvl temp(N, vl (N, 0));

	for(int i = 0; i < N; i++) {

		for(int j = 0; j < N; j++) {

			for(int k = 0; k < N; k++) {

				temp[i][j] = ad(temp[i][j], ml(F[i][k], R[k][j]));

			}

		}

	}

	F = temp;

}



void mpow(vvl &F, ll N, ll n) {

	vvl res(N, vl (N, 0));

	for(int i = 0; i < N; i++) res[i][i] = 1;

	while(n) {

		if(n&1) multiply(res, F, N);

		multiply(F, F, N);

		n >>= 1;

	}

	F = res;

}



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

   	int s;

   	cin >> s;

   	vvl F = {{1,0,1},{1,0,0},{0,1,0}};

   	if(s>=3) mpow(F, 3, s-3);

 	cout << (s>=3 ? F[0][0] : 0) << "\n";

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)

#define chmax(x,y) x=max(x,y)

#define chmin(x,y) x=min(x,y)

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int mod = 1000000007;

const int INF = 1001001001;



struct mint {

  ll x; // typedef long long ll;

  mint(ll x=0):x((x%mod+mod)%mod){}

  mint operator-() const { return mint(-x);}

  mint& operator+=(const mint a) {

    if ((x += a.x) >= mod) x -= mod;

    return *this;

  }

  mint& operator-=(const mint a) {

    if ((x += mod-a.x) >= mod) x -= mod;

    return *this;

  }

  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}

  mint operator+(const mint a) const { return mint(*this) += a;}

  mint operator-(const mint a) const { return mint(*this) -= a;}

  mint operator*(const mint a) const { return mint(*this) *= a;}

  mint pow(ll t) const {

    if (!t) return 1;

    mint a = pow(t>>1);

    a *= a;

    if (t&1) a *= *this;

    return a;

  }



  // for prime mod

  mint inv() const { return pow(mod-2);}

  mint& operator/=(const mint a) { return *this *= a.inv();}

  mint operator/(const mint a) const { return mint(*this) /= a;}

};

istream& operator>>(istream& is, const mint& a) { return is >> a.x;}

ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}



struct combination {

  vector<mint> fact, ifact;

  combination(int n):fact(n+1),ifact(n+1) {

    assert(n < mod);

    fact[0] = 1;

    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;

    ifact[n] = fact[n].inv();

    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;

  }

  mint operator()(int n, int k) {

    if (k < 0 || k > n) return 0;

    return fact[n]*ifact[k]*ifact[n-k];

  }

};



int main() {

  int n;

  cin >> n;

  mint ans = 0;

  combination comb(100000);

  for (int i = 1; i <= n; ++i) {

    int cur = n - i * 3;

    if (cur < 0) break;

    ans += comb(cur + i - 1, i - 1);

  }

  cout << ans << endl;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)

#define chmax(x,y) x=max(x,y)

#define chmin(x,y) x=min(x,y)

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int mod = 1000000007;

const int INF = 1001001001;



int dp[3010];



int main() {

  int n;

  cin >> n;

  dp[0] = 1;

  for (int i = 1; i <= n; ++i) for (int j = i - 3; j >= 0; --j) {

    dp[i] += dp[j];

    dp[i] %= mod;

  }



  cout << dp[n] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+10;

ll dp[N];

ll n;

const int mod = 1e9+7;

ll solve(ll j) {

	if(j==n) {

		return dp[j] = 1;

	}

	if(j>n) return dp[j]=0;

	if(dp[j]!=-1) {

		return dp[j];

	}	

	int ret=0;

	for(int i=3;i<=n-j;i++) {

		ret = (ret+solve(j+i))%mod;

	}

	return dp[j] = ret;

}

int main() {

	memset(dp,-1,sizeof(dp));

	cin>>n;

	ll ans=0;

	cout<<solve(0)<<endl;

    return 0;

} 

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5+10;

const int mod = 1e9+7;

ll dp[N];

ll a[N];

int main() {

	int n;

	cin>>n;

	for(int i=1;i<=n;i++) {

		if(i==1||i==2) dp[i] = 0;

		else if(i==3) {

			dp[i] = 1;

		}

		else {

			dp[i] = (dp[i-3]+dp[i-1])%mod;

		}

	}

	cout<<dp[n]<<endl;

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

ll dp[20009];

ll n,m;

ll call(ll rem)

{

    if(rem==0)

    {

        return 1;

    }

    if(rem==1 || rem==2)

    {

        return 0;

    }

    if(dp[rem]!=-1)

    {

        return dp[rem];

    }

    ll i,x,y;

    x=0;

    for(i=3;i<=rem;i++)

    {

        y=call(rem-i);

        x=(x+y)%m;

    }

    return dp[rem]=x%m;

}

int main()

{

    ll a,b,c,d,e,i,j,k,l,x,y,t,p;

    m=(1e9)+7;

    cin>>n;

    if(n<3)

    {

        printf("0\n");

        return 0;

    }

    memset(dp,-1,sizeof(dp));

    x=call(n);

    x=x%m;

    cout<<x<<endl;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

ll dp[2009];

ll n,m;

ll call(ll rem)

{

    if(rem==0)

    {

        return 1;

    }

    if(rem==1 || rem==2)

    {

        return 0;

    }

    if(dp[rem]!=-1)

    {

        return dp[rem];

    }

    ll i,x,y;

    x=0;

    for(i=3;i<=rem;i++)

    {

        y=call(rem-i);

        x=(x+y)%m;

    }

    return dp[rem]=x%m;

}

int main()

{

    ll a,b,c,d,e,i,j,k,l,x,y,t,p;

    m=(1e9)+7;

    cin>>n;

    if(n<3)

    {

        printf("0\n");

        return 0;

    }

    memset(dp,-1,sizeof(dp));

    x=call(n);

    x=x%m;

    cout<<x<<endl;

}


// Fastest known solution for this problem: