stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.283190217760955x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.233377326074437x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.6248270735049637x):
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

long long int sum=0;

int a[100001];

long long int n,j,ans;

int pd(int i)

{	

	//for(j=0;j<=i;j++)

	sum+=a[i];

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

	{

		if(2*sum>=a[j])

		sum+=a[j];

		else

		return j;

	}

	return 0;

}

int main()

{

	int i,s;

	cin>>n;

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

	{

		cin>>a[i];

	}

	sort(a,a+n);

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

	{	s=pd(i);

		if(!s)

		break;

		i=s-1;

	}

	ans=n-i;

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.6643405792397954x):
#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; 

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.606428496092296x):
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast", "unroll-loops")

#define ll long long 

#define ull unsigned ll

#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

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

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

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

#define f first

#define s second

#define pii pair<int,int>

#define SQ(x) (x)*(x);

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

#define pb push_back

#define endl '\n'

using namespace std;

main (){

	int n; cin>>n;

	vector<int> vc(n);

	REP(i,n) cin>>vc[i];

	sort(ALL(vc));

	vector<ll> prsum(n);

	prsum[0]=vc[0];

	REP1(i,n-1){

		prsum[i]=prsum[i-1]+vc[i];

	}

	int cnt=0;

	REP(i,n-1){

		if (prsum[i]*2<vc[i+1]) cnt=0;

		else cnt++;

	}

	cout<<cnt+1<<endl;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.576346961482851x):
#include <bits/stdc++.h>

using namespace std;

#define INF 2000000000

typedef long long int ll;

typedef pair<ll,ll> ii;

typedef pair<ii,ll> iii;

typedef vector<ll> vi;

typedef vector<ii> vii;

#define getbit(n,i) (((n)&(1LL<<(i)))!=0)

#define setbit0(n,i) ((n)&(~(1LL<<(i))))

#define setbit1(n,i) ((n)|(1LL<<(i)))

#define lastone(n) ((n)&(-(n)))

#define read freopen("debug\\in.txt","r",stdin)

#define write freopen("debug\\out.txt","w",stdout)

#define DBG(a) cout<<#a<<" ->->->-> "<<a<<"\n"

#define fi first

#define se second

#define PI (acos(-1))

#define fastread ios::sync_with_stdio(false);cin.tie(NULL)

#define mod (1000000007)

#define asz 500005

template<class T,class V> ostream& operator<<(ostream &s,pair<T,V> a)

{

    s<<a.fi<<' '<<a.se;

    return s;

}

int main()

{

    fastread;

    ll T=1;

//    cin>>T;

    for(ll qq=1;qq<=T;qq++)

    {

        ll n;

        cin>>n;

        vi a(n);

        for(auto &x:a)cin>>x;

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

        ll lo=0,hi=n-1;

        while(lo<hi){

            ll mid=(lo+hi)/2;

            ll cur=2*a[mid];

            int i=0;

            for(;i<n;i++){

                if(i==mid)continue;

                if(a[i]>cur)break;

                cur+=2*a[i];

            }

            if(i==n)hi=mid;

            else lo=mid+1;

        }

        cout<<n-lo<<endl;

    }

    return 0;

}
// Slower C++ solution:
#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;

}




// Faster C++ solution for the same problem (measured speedup: 1.702027652688641x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.40560897426759x):
#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;

}
// Slower C++ solution:
//#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.6490242775153257x):
//#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.9497823678384647x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 3.65824178163773x):
#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;

}
// Slower C++ solution:
#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;

} 

// Faster C++ solution for the same problem (measured speedup: 1.9147173639125918x):
#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;

}