stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
/************************************************************************/

/****															*********/

/****                          Writer:孙~~                      *********/

/****                            Lang:C++                       *********/

/****                          Status:Unknow                    *********/

/****															*********/

/************************************************************************/

#include <iostream>

#include <string>

#include <cstdio>

#include <vector>

#include <queue>

#include <list>

#include <cstdlib>

#include <algorithm>

#include <set>

#include <map>

#include <deque>

#include <cstring>

#include <cmath>

//#include<bits/stdc++.h>

#define debug(...) if(debug) printf(__VA_ARGS__)

using namespace std;



const int INF=0x3f3f3f3f;

const int SIZE=100005;

const bool debug=false;



int dp[SIZE];

vector<int> mp[SIZE];

int dig[SIZE];



int n;



void visit(int p,int f){

	int s=0,cnt=0;

	for(int i=0;i<mp[p].size();i++){

		int u=mp[p][i];

		if(u==f) continue;

		visit(u,p);

		if(dp[u]==0) cnt++;

		s+=dp[u];

	}

//	if(p==1) debug("%d\n",leave);

	dp[p]=s+max(0,cnt-1);

}



int main(){

	scanf("%d",&n);

	for(int a,b,i=0;i<n-1;i++){

		scanf("%d",&a);

		scanf("%d",&b);

		mp[a].push_back(b);

		mp[b].push_back(a);

		dig[a]++;

		dig[b]++;

	}

	int root=-1,mx=0;

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

		if(dig[i]>mx) root=i,mx=dig[i];

	}

	if(mx<=2){

		puts("1");

		return 0;

	}

	visit(root,-1);

	for(int i=0;i<n;i++) debug("%d ",dp[i]);

	debug("\n");

	printf("%d\n",dp[root]);

	return 0;

}


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

#include<cstdio>

#include<algorithm>

using namespace std;

struct node{

	int ne,tow;

};

node pth[200000+10];

int mp[100000+10],szp;

int vis[100000+10];

int n;

int deg[100000+10];

int root=-1;

int son[100000+10];

int bro[100000+10];

int dp[100000+10];

int left[100000+10];

void addpath(int i,int j){

	++szp;

	pth[szp].ne=mp[i];

	pth[szp].tow=j;

	mp[i]=szp;

	deg[i]++;

}



void dfs1(int i,int j){

	if (vis[i]!=0) return;

	vis[i]=j;

	int po=mp[i];

	while (po!=-1){

		if (vis[pth[po].tow]==0){

			bro[pth[po].tow]=son[i];

			son[i]=pth[po].tow;

		}

		dfs1(pth[po].tow,j+1);

		po=pth[po].ne;

	}	

}

void dfs2(int i){

	int j=son[i];

	if (j==-1){

		left[i]=1;

		dp[i]=1;

		return;

	}

	while (j!=-1){

		dfs2(j);

		left[i]+=left[j];

		dp[i]+=dp[j];

		j=bro[j];

	}

	j=son[i];

	if (j!=-1&&bro[j]!=-1)

	while (j!=-1){

		if (dp[j]==1&&left[j]==1){

			dp[i]--;

			return;

		}

		j=bro[j];

	}



}





int main(){

	scanf("%d",&n);

	for (int f1=0;f1<n;f1++){

		mp[f1]=-1;

		vis[f1]=0;

	}

	

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

		int i,j;

		scanf("%d%d",&i,&j);

		addpath(i,j);

		addpath(j,i);

		if (deg[i]>2)root=i;

		if (deg[j]>2)root=j;

	}

	if (root==-1){

		printf("1\n");

		return 0;

	}

	for (int f1=0;f1<n;f1++){

		son[f1]=-1;

		bro[f1]=-1;

		left[f1]=0;

		dp[f1]=0;

	}

	dfs1(root,1);

	dfs2(root);

	printf("%d\n",dp[root]);

	//for (int f1=0;f1<n;f1++)printf("%d ",dp[f1]);

}


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

using namespace std;

 

int n, x, y, res, fir=1, rt, f[101000];

vector<int>G[101000];

 

void dfs(int x,int fff){

  int isrt=0;

  if (G[x].size()>2&&fir) fir=0, isrt=1;

  for (auto y:G[x]) if (y!=fff) dfs(y,x);

  int t=max(0,(int)G[x].size()+isrt-2-f[x]);

  f[fff]+=!!f[x]|!!t;

  res+=t;

}

 

int main(){

  cin>>n;

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

    scanf("%d%d",&x,&y); ++x; ++y;

    G[x].push_back(y); G[y].push_back(x);

  }

  for (rt=1;G[rt].size()!=1;++rt); dfs(rt,0);

  cout<<max(res,1);

}

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

#include<cstdio>

#include<algorithm>

using namespace std;

struct node{

	int ne,tow;

};

node pth[200000+10];

int mp[100000+10],szp;

int vis[100000+10];

int n;

int deg[100000+10];

int root=-1;

int son[100000+10];

int bro[100000+10];

int dp[100000+10];

int left[100000+10];

void addpath(int i,int j){

	++szp;

	pth[szp].ne=mp[i];

	pth[szp].tow=j;

	mp[i]=szp;

	deg[i]++;

}



void dfs1(int i,int j){

	if (vis[i]!=0) return;

	vis[i]=j;

	int po=mp[i];

	while (po!=-1){

		if (vis[pth[po].tow]==0){

			bro[pth[po].tow]=son[i];

			son[i]=pth[po].tow;

		}

		dfs1(pth[po].tow,j+1);

		po=pth[po].ne;

	}	

}

void dfs2(int i){

	int j=son[i];

	if (j==-1){

		left[i]=1;

		dp[i]=1;

		return;

	}

	while (j!=-1){

		dfs2(j);

		left[i]+=left[j];

		dp[i]+=dp[j];

		j=bro[j];

	}

	j=son[i];

	if (j!=-1&&bro[j]!=-1)

	while (j!=-1){

		if (dp[j]==1&&left[j]==1){

			dp[i]--;

			return;

		}

		j=bro[j];

	}



}





int main(){

	scanf("%d",&n);

	for (int f1=0;f1<n;f1++){

		mp[f1]=-1;

		vis[f1]=0;

	}

	

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

		int i,j;

		scanf("%d%d",&i,&j);

		addpath(i,j);

		addpath(j,i);

		if (deg[i]>2)root=i;

		if (deg[j]>2)root=j;

	}

	if (root==-1){

		printf("1\n");

		return 0;

	}

	for (int f1=0;f1<n;f1++){

		son[f1]=-1;

		bro[f1]=-1;

		left[f1]=0;

		dp[f1]=0;

	}

	dfs1(root,1);

	dfs2(root);

	printf("%d\n",dp[root]);

	//for (int f1=0;f1<n;f1++)printf("%d ",dp[f1]);

}


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

using namespace std;

const int N = 1e5 + 5;

int n;

struct Edge {

	int to;

	int next;

}edge[N * 2];

int head[N];

int cnt;

void AddEdge(int fr, int to) {

	edge[++cnt].to = to;

	edge[cnt].next = head[fr];

	head[fr] = cnt;

}

int d[N];

int DFS(int x, int fa) {

	int t = d[x] - 1;

	if (fa != 0) t--;

	int re = 0;

	for (int i = head[x]; i; i = edge[i].next) {

		if (edge[i].to != fa) {

			int tmp = DFS(edge[i].to, x);

			re += tmp;

			if (tmp) t--;

		}

	}

	re += max(t, 0);

	//cerr << x << " " << re << endl;

	return re;

}

int main() {

	scanf("%d", &n);

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

		scanf("%d%d", &a, &b);

		d[++a]++;

		d[++b]++;

		AddEdge(a, b);

		AddEdge(b, a);

	}

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

		if (d[i] > 2) {

			printf("%d\n", DFS(i, 0));

			return 0;

		}

	}

	printf("1\n");

	return 0;

}

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

#include<cstdio>

#include<algorithm>

using namespace std;

struct node{

	int ne,tow;

};

node pth[200000+10];

int mp[100000+10],szp;

int vis[100000+10];

int n;

int deg[100000+10];

int root=-1;

int son[100000+10];

int bro[100000+10];

int dp[100000+10];

int left[100000+10];

void addpath(int i,int j){

	++szp;

	pth[szp].ne=mp[i];

	pth[szp].tow=j;

	mp[i]=szp;

	deg[i]++;

}



void dfs1(int i,int j){

	if (vis[i]!=0) return;

	vis[i]=j;

	int po=mp[i];

	while (po!=-1){

		if (vis[pth[po].tow]==0){

			bro[pth[po].tow]=son[i];

			son[i]=pth[po].tow;

		}

		dfs1(pth[po].tow,j+1);

		po=pth[po].ne;

	}	

}

void dfs2(int i){

	int j=son[i];

	if (j==-1){

		left[i]=1;

		dp[i]=1;

		return;

	}

	while (j!=-1){

		dfs2(j);

		left[i]+=left[j];

		dp[i]+=dp[j];

		j=bro[j];

	}

	j=son[i];

	if (j!=-1&&bro[j]!=-1)

	while (j!=-1){

		if (dp[j]==1&&left[j]==1){

			dp[i]--;

			return;

		}

		j=bro[j];

	}



}





int main(){

	scanf("%d",&n);

	for (int f1=0;f1<n;f1++){

		mp[f1]=-1;

		vis[f1]=0;

	}

	

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

		int i,j;

		scanf("%d%d",&i,&j);

		addpath(i,j);

		addpath(j,i);

		if (deg[i]>2)root=i;

		if (deg[j]>2)root=j;

	}

	if (root==-1){

		printf("1\n");

		return 0;

	}

	for (int f1=0;f1<n;f1++){

		son[f1]=-1;

		bro[f1]=-1;

		left[f1]=0;

		dp[f1]=0;

	}

	dfs1(root,1);

	dfs2(root);

	printf("%d\n",dp[root]);

	//for (int f1=0;f1<n;f1++)printf("%d ",dp[f1]);

}


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

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN = 100000;

vector<int>G[MAXN + 5];

void addedge(int u, int v) {

	G[u].push_back(v);

	G[v].push_back(u);

}

int dp[MAXN + 5];

void dfs(int rt, int pre) {

	int cnt = 0;bool flag = 0;

	for(int i=0;i<G[rt].size();i++)

		if( G[rt][i] != pre ) {

			int p = G[rt][i];

			dfs(p, rt);

			if( dp[p] == 0 ) {

				if( !flag ) flag = true;

				else dp[rt]++;

			}

			else

				dp[rt] += dp[p];

		}

}

int main() {

	int N, root = -1;

	scanf("%d", &N);

	for(int i=1;i<=N-1;i++) {

		int a, b;

		scanf("%d%d", &a, &b);

		addedge(a, b);

	}

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

		if( G[i].size() > 2 )

			root = i;

	if( root == -1 ) {

		printf("1\n");

		return 0;

	}

	dfs(root, -1);

	printf("%d\n", dp[root]);

}

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

#include<cstdio>

#include<algorithm>

using namespace std;

struct node{

	int ne,tow;

};

node pth[200000+10];

int mp[100000+10],szp;

int vis[100000+10];

int n;

int deg[100000+10];

int root=-1;

int son[100000+10];

int bro[100000+10];

int dp[100000+10];

int left[100000+10];

void addpath(int i,int j){

	++szp;

	pth[szp].ne=mp[i];

	pth[szp].tow=j;

	mp[i]=szp;

	deg[i]++;

}



void dfs1(int i,int j){

	if (vis[i]!=0) return;

	vis[i]=j;

	int po=mp[i];

	while (po!=-1){

		if (vis[pth[po].tow]==0){

			bro[pth[po].tow]=son[i];

			son[i]=pth[po].tow;

		}

		dfs1(pth[po].tow,j+1);

		po=pth[po].ne;

	}	

}

void dfs2(int i){

	int j=son[i];

	if (j==-1){

		left[i]=1;

		dp[i]=1;

		return;

	}

	while (j!=-1){

		dfs2(j);

		left[i]+=left[j];

		dp[i]+=dp[j];

		j=bro[j];

	}

	j=son[i];

	if (j!=-1&&bro[j]!=-1)

	while (j!=-1){

		if (dp[j]==1&&left[j]==1){

			dp[i]--;

			return;

		}

		j=bro[j];

	}



}





int main(){

	scanf("%d",&n);

	for (int f1=0;f1<n;f1++){

		mp[f1]=-1;

		vis[f1]=0;

	}

	

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

		int i,j;

		scanf("%d%d",&i,&j);

		addpath(i,j);

		addpath(j,i);

		if (deg[i]>2)root=i;

		if (deg[j]>2)root=j;

	}

	if (root==-1){

		printf("1\n");

		return 0;

	}

	for (int f1=0;f1<n;f1++){

		son[f1]=-1;

		bro[f1]=-1;

		left[f1]=0;

		dp[f1]=0;

	}

	dfs1(root,1);

	dfs2(root);

	printf("%d\n",dp[root]);

	//for (int f1=0;f1<n;f1++)printf("%d ",dp[f1]);

}


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

using namespace std;

const int boss=1e5;

int n,m,vis[boss+10];

vector<int> lj[boss+10];

int dfs(int u,int fa)

{

if (lj[u].size()>2) return u;

for (int i:lj[u]) if (i!=fa) return dfs(i,u);

return u;

}

int main()

{

int i,u,v;

scanf("%d",&n);

for (i=1;i<n;i++) scanf("%d%d",&u,&v),u++,v++,lj[u].push_back(v),lj[v].push_back(u);

for (i=1;i<=n;i++) if (lj[i].size()==1) vis[dfs(i,0)]=1,m++;

for (i=1;i<=n;i++) if (vis[i]) m--;

printf("%d",max(m,1));

}

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

#include<cstdio>

using namespace std;

int d[101010];

struct Edge{

	int to,next;

}e[202020];

int cnt=0,head[101010];

void add(int u,int v)

{

	cnt++;

	e[cnt].to=v;

	e[cnt].next=head[u];

	head[u]=cnt;

}

int f[101010],g[101010];

int dis[101010];

void cal(int x,int fa)

{

	for(int i=head[x];i!=0;i=e[i].next)

	{

		int to=e[i].to;

		if(to!=fa)

		{

			dis[to]=dis[x]+1;

			cal(to,x);

		}

	}

}

void dfs(int x,int fa)

{

	int dd=0;

	for(int i=head[x];i!=0;i=e[i].next)

	{

		int to=e[i].to;

		if(to!=fa)

		{

			dfs(to,x);

			f[x]+=f[to];

			if(f[to]==0)

				dd++;

		}

	}

	if(dd>0)

		f[x]+=dd-1;

}

int main()

{

	int n;

	scanf("%d",&n);

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

	{

		int u,v;

		scanf("%d%d",&u,&v);

		u++;

		v++;

		d[u]++;

		d[v]++;

		add(u,v);

		add(v,u);

	}

	cal(1,1);

	int mx=1;

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

	if(dis[i]>dis[mx])

		mx=i;

	dfs(mx,mx);

	printf("%d\n",f[mx]+1);

	return 0;

}

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

#include<vector>



using namespace std;



vector<int>g[100001];

int a[100001],ans;

void dfs(int u,int f){

	int z=0;

	for(int i=0;i<g[u].size();i++)

		if(g[u][i]!=f){

			dfs(g[u][i],u);

			z+=!a[g[u][i]];

			a[u]|=a[g[u][i]];

		}

	if(z>1)ans+=z-1,a[u]=1;

}

int main(){

	int n;

	scanf("%d",&n);

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

		int u,v;

		scanf("%d%d",&u,&v);

		u++;v++;

		g[u].push_back(v);

		g[v].push_back(u);

	}

	int o=1;

	while(o<=n&&g[o].size()!=1)o++;

	if(o>n){

		printf("1\n");

		return 0;

	}

	dfs(o,0);

	int haha=ans+1;

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

		o++;

		while(o<=n&&g[o].size()!=1)o++;

		if(o>n)break;

		ans=0;

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

		dfs(o,0);

		haha=min(haha,ans+1);

	}

	printf("%d\n",haha);

}


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

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>



using namespace std;



#define N 100008



int n, top, ans;

int f[N], son[N], fa[N], vis[N];

struct road

{

    int next, to;

}r[2*N];



void build(int u, int v)

{

    r[++top].to = v;

    r[top].next = f[u];

    f[u] = top;

}



int dfs(int now, int fa)

{

    if (son[now] > 2)   return now;

    for (int i = f[now]; i; i = r[i].next)

    {

        if (r[i].to == fa) continue;

        now = dfs(r[i].to, now);

    }

    return now;

}



void solve()

{

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

    {

        if (son[i] == 1)

        {

            vis[dfs(i, -1)] = 1;

            ans++;

        }

    }

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

        if (vis[i] == 1)

            ans--;

    ans = max(ans, 1);

}



int main()

{

    int x, y;

    while (~scanf("%d", &n))

    {

        top = ans = 0;

        memset(f, 0, sizeof(f));

        memset(vis, 0, sizeof(vis));

        memset(son, 0, sizeof(son));

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

        {

            scanf("%d%d", &x, &y);

            son[x]++;

            son[y]++;

            build(x, y);

            build(y, x);

        }

        solve();

        printf("%d\n", ans);

    }

    return 0;

}

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

#include<vector>

using namespace std;

const int MAXN=100005;



vector<int> adj[MAXN];

int deg[MAXN];



int dfs(int u,int fa=-1)

{

	int res=0,temp;

	bool flag=false;

	for(int i=0;i<(int)adj[u].size();i++)

	{

		int v=adj[u][i];

		if(v==fa)

			continue;

		temp=dfs(v,u);

		if(temp==0&&flag==true)

			temp++;

		if(temp==0&&flag==false)

			flag=true;

		res+=temp;

	}

	return res;

}



int main()

{

	int N;

	scanf("%d",&N);

	for(int i=0,u,v;i<N-1;i++)

	{

		scanf("%d%d",&u,&v);

		deg[u]++;

		deg[v]++;

		adj[u].push_back(v);

		adj[v].push_back(u);

	}

	int root=-1;

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

		if(deg[i]>=3)

		{

			root=i;

			break;

		}

	if(root==-1)

		puts("1");

	else

		printf("%d\n",dfs(root));

	return 0;

}


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

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>



using namespace std;



#define N 100008



int n, top, ans;

int f[N], son[N], fa[N], vis[N];

struct road

{

    int next, to;

}r[2*N];



void build(int u, int v)

{

    r[++top].to = v;

    r[top].next = f[u];

    f[u] = top;

}



int dfs(int now, int fa)

{

    if (son[now] > 2)   return now;

    for (int i = f[now]; i; i = r[i].next)

    {

        if (r[i].to == fa) continue;

        now = dfs(r[i].to, now);

    }

    return now;

}



void solve()

{

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

    {

        if (son[i] == 1)

        {

            vis[dfs(i, -1)] = 1;

            ans++;

        }

    }

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

        if (vis[i] == 1)

            ans--;

    ans = max(ans, 1);

}



int main()

{

    int x, y;

    while (~scanf("%d", &n))

    {

        top = ans = 0;

        memset(f, 0, sizeof(f));

        memset(vis, 0, sizeof(vis));

        memset(son, 0, sizeof(son));

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

        {

            scanf("%d%d", &x, &y);

            son[x]++;

            son[y]++;

            build(x, y);

            build(y, x);

        }

        solve();

        printf("%d\n", ans);

    }

    return 0;

}

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

#include<set>

#include<vector>

#include<algorithm>

#include<string>

#include<sstream>

#include<map>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

#include<stack>

#include<utility> 

#include<fstream>

#include<cassert>

#include<cstdlib>

#include<deque>

#include<list>

#include<bitset>

#include<cassert>

#include<functional>

using namespace std;

int n,dp[100005];

vector<int> nei[100005];

void dfs(int v,int pa)

{

	int cnt=0;

	for(int i=0;i<nei[v].size();i++)

	{

		int u=nei[v][i];

		if(u==pa) continue;

		dfs(u,v);

		

		if(dp[u]==0) cnt++;else dp[v]+=dp[u];

	}

	if(cnt>1) dp[v]+=cnt-1;

	dp[v]=max(dp[v],0);

}

int main()

{

	cin>>n;

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

	{

		int x,y;

		scanf("%d %d",&x,&y);

		nei[x].push_back(y);

		nei[y].push_back(x);

	}

	bool flag=0;

	int ro=-1;

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

	{

		if(nei[i].size()>=3) ro=i; 

	}

	if(ro==-1)

	{

		cout<<1;

		return 0;

	}

	dfs(ro,-1);

	cout<<dp[ro];

}

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

#include<set>

#include<vector>

#include<algorithm>

#include<string>

#include<sstream>

#include<map>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

#include<stack>

#include<utility> 

#include<fstream>

#include<cassert>

#include<cstdlib>

#include<deque>

#include<list>

#include<bitset>

#include<cassert>

#include<functional>

using namespace std;

int n,dp[100005],la[100005],pre[200005],va[200005],deg[100005];

//vector<int> nei[100005];

void dfs(int v,int pa)

{

	int cnt=0;

	for(int i=la[v];i!=-1;i=pre[i])

	{

		int u=va[i];

		if(u==pa) continue;

		dfs(u,v);

		if(dp[u]==0) cnt++;else dp[v]+=dp[u];

	}

	if(cnt>1) dp[v]+=cnt-1;

	dp[v]=max(dp[v],0);

}

int main()

{

	cin>>n;

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

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

	{

		int x,y;

		scanf("%d %d",&x,&y);

		pre[2*i]=la[x];

		va[2*i]=y;

		la[x]=2*i;

		pre[2*i+1]=la[y];

		va[2*i+1]=x;

		la[y]=2*i+1;

		deg[x]++;deg[y]++;

	}

	bool flag=0;

	int ro=-1;

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

	{

		if(deg[i]>=3) ro=i; 

	}

	if(ro==-1)

	{

		cout<<1;

		return 0;

	}

	dfs(ro,-1);

	cout<<dp[ro];

}

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

using namespace std;



#define Omar45 ios_base::sync_with_stdio(false); cin.tie(NULL);

#define ll long long

#define pb push_back

#define F first

#define S second

#define endl '\n'

const ll mod = 1e9 + 7;

const ll maxN = 1e5 + 5;

const ll INF = 1e18;



int n, k, dp[maxN], val[maxN], arr[103];



int main() {

	Omar45

    int n, k; cin >> n >> k;

    vector <ll> arr(n);

    for (int i=0; i<n; i++) cin >> arr[i];

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

    dp[0][0] = 1;

    for (int child=0; child<n; child++) {

        ll sum = 0;

        for (int usedCandy = 0; usedCandy<k+1; usedCandy++) {

            sum += dp[child][usedCandy];

            if (usedCandy > arr[child])

                sum -= dp[child][usedCandy-arr[child]-1];

            sum = (sum + mod) %mod;

            dp[child+1][usedCandy] = (dp[child+1][usedCandy] % mod + sum % mod ) % mod;

        }

    }

    cout << dp[n][k] << endl;

}

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

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

//#define x first

//#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

int mod = 1e9 + 7;

int dp[109][100009];

int main(){

    cin.tie(0);

    cin.sync_with_stdio(0);



    int n,k;

    cin>>n>>k;



    vector<int> a(n);

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

        cin>>a[i];







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

        dp[i][0]= 1;



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

        int sums[k + 1];

        sums[0] = dp[i + 1][0];

        for(int j = 1; j <= k; j++)

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



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

            int sum  = sums[j];

            if(j - a[i] - 1 >= 0) sum = (sum - sums[j - a[i] - 1] + mod)%mod;



            dp[i][j] = sum;

            //dp[i][j] = dp[i + 1][j - x : 0 <= x <= a[i]]

        }

    }



    cout<<dp[0][k];

}


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

#define int long long

#define pb push_back

#define pii pair<int,int>

#define vi vector<int>

#define vii vector<pii>

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

#define X first

#define Y second

#define inf 2e9+5

using namespace std;

const int mod=1e9+7;

void solve()

{

  int n,k; cin>>n>>k; int a[n];

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

  int dp[k+1]={0}; dp[0]=1;

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

  {

      int cnt=0;

      for(int j=k;j>=k-a[i];j--){cnt+=dp[j]; cnt%=mod;}

      for(int j=k;j>=0;j--)

      {

          int t=dp[j];

          dp[j]=cnt;

          cnt-=t;

          if(j-a[i]-1>=0)cnt+=dp[j-a[i]-1];

          cnt=(cnt+mod)%mod;

      }

  }

  cout<<dp[k];

  return;

}

signed main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int t; t=1;

    while(t--)solve();

    return 0;

}


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

#define ll long long

#define pb push_back

#define pii pair<int,int>

#define vi vector<int>

#define vii vector<pii>

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

#define X first

#define Y second

using namespace std;

const int mod=1e9+7;

void solve()

{

    int n,k; cin>>n>>k;

    int a[n],b[k+1]; b[0]=1;

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

    int dp[k+1];

    memset(dp,0,sizeof(dp));

    dp[0]=1;

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

    {

        for(int j=1;j<=k;j++)b[j]=(dp[j]+b[j-1])%mod;

        for(int j=1;j<=k;j++)

        {

            if(j-a[i]-1<0)dp[j]=b[j];

            else dp[j]=(b[j]-b[j-a[i]-1]+mod)%mod;

        }

    }

    cout<<dp[k];

    return;

}

signed main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int t; t=1;

    while(t--)solve();

    return 0;

}


// Fastest known solution for this problem: