stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<algorithm>



#define INF 100000000

 

using namespace std;



int gcd(int a,int b){

	if(b==0)return a;

	return gcd(b,a%b);

}

 

int V,match[1001];

bool used[1001];

vector<int>G[1001];

 

void add_edge(int u,int v){

  G[u].push_back(v);

  G[v].push_back(u);

}

 

bool dfs(int v){

  used[v]=true;

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

    int u=G[v][i],w=match[u];

    if(w<0 || !used[w] && dfs(w)){

      match[v]=u;

      match[u]=v;

      return true;

    }

  }

  return false;

}

 

int bipartite_matching(){

  int res=0;

  fill(match,match+1001,-1);

  for(int v=0;v<V;v++){

    if(match[v]<0){

      fill(used,used+1001,false);

      if(dfs(v))res++;

    }

  }

  return res;

}

 

int main(void){

	

	int m,n;

	

	while(cin >> m >> n,m|n){

		vector<int>b(m),r(n);

		for(int i=0;i<1001;i++)G[i].clear();

		

		for(int i=0;i<m;i++)cin >> b[i];

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

		

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

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

				if(gcd(b[i],r[j])!=1)add_edge(i,j+m);

			}

		}

		V=max(m,n);

		cout << bipartite_matching() << endl;

	}

	

return 0;

}

 

// Faster C++ solution for the same problem (measured speedup: 1.183051338058365x):
#include <algorithm>

#include <iostream>

#include<vector>



#define MAXN1 50000

#define MAXN2 50000

#define MAXM 150000



using namespace std;



int n1, n2, edges, last[MAXN1];

int preve[MAXM];

int head[MAXM];

int matching[MAXN2], dist[MAXN1], Q[MAXN1];

bool used[MAXN1], vis[MAXN1];



void init(int _n1, int _n2) {

  n1=_n1;

  n2=_n2;

  edges=0;

  fill(last, last + n1, -1);

}



void add_edge(int u, int v) {

  head[edges]=v;

  preve[edges] = last[u];

  last[u] = edges++;

}



void bfs() {

  fill(dist,dist+n1,-1);

  int sizeQ=0;

  for (int u=0;u<n1;u++) {

    if (!used[u]) {

      Q[sizeQ++]=u;

      dist[u]=0;

    }

  }

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

    int u1 = Q[i];

    for (int e=last[u1];e>=0;e=preve[e]) {

      int u2 = matching[head[e]];

      if (u2>=0 && dist[u2]<0) {

	dist[u2]=dist[u1]+1;

	Q[sizeQ++]=u2;

      }

    }

  }

}



bool dfs(int u1) {

  vis[u1]=true;

  for (int e=last[u1];e>=0;e=preve[e]) {

    int v=head[e];

    int u2=matching[v];

    if (u2<0 || (!vis[u2] && dist[u2]==dist[u1]+1 && dfs(u2))) {

      matching[v]=u1;

      return used[u1]=true;

    }

  }

  return false;

}



int bipartite_matching() {

  fill(used,used+n1,false);

  fill(matching,matching+n2,-1);

  for (int res=0;;) {

    bfs();

    fill(vis,vis+n1,false);

    int f=0;

    for(int u=0;u<n1;u++)

      if(!used[u] && dfs(u))f++;

    if (!f)return res;

    res+=f;

  }

}



int gcd(int a,int b){

    if(b==0)return a;

    return gcd(b,a%b);

}



int main(void){

  

  int m,n;

  

  while(cin >> m >> n,m|n){

 

    init(m,n);

    

    vector<int>b(m),r(n);

    for(int i=0;i<m;i++)cin >> b[i];

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

    

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

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

	if(gcd(b[i],r[j])!=1)add_edge(i,j);

      }

    }



    cout << bipartite_matching() << endl;

  }

  

  return 0;

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<algorithm>

#include<cstring>

using namespace std;



#define V_MAX 1100

#define INF (1<<25)

#define pb push_back

#define sz size()

#define clr clear()



struct edge{int f,t,cost,cap,rev;};



vector<edge> G[V_MAX];

bool use[V_MAX];

int m,n;

int b[500],r[500];





void AddEdge(int from,int to,int cap){

  G[from].push_back((edge){from,to,0,cap,G[to].size()});

  G[to].push_back((edge){to,from,0,0,G[from].size()-1});

}



int dfs(int v,int t,int f){

  if(v==t)return f;

  use[v] = true;

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

    edge &e  = G[v][i];

    if(!use[e.t] && e.cap > 0){

      int d = dfs(e.t, t,min(f,e.cap));

      if(d>0){

	e.cap -= d;

	G[e.t][e.rev].cap += d;

	return d;

      }

    }

  }

  return 0;

}



int FordFullkerson(int s,int t){

  int flow = 0;

  for(;;){

    memset(use,0,sizeof(use));

    int tmp = dfs(s,t,INF);

    if(!tmp)return flow;

    flow += tmp;

  }

} 



int gcd(int a,int b){

  if(!b)return a;

  return gcd(b,a%b);

}



int main(){

  while(1){

    cin >> m >> n;

    if(!m && !n)break;



    for(int i=0;i<m;i++)cin >> b[i];

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



    for(int i=0;i<=m+n+1;i++)G[i].clr;

    for(int i=1;i<=m;i++)AddEdge(0,i,1);

    for(int i=m+1;i<=m+n;i++)AddEdge(i,m+n+1,1);



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

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

	if(gcd(b[i],r[j])>1)AddEdge(i+1,m+j+1,1);



    cout << FordFullkerson(0,m+n+1) << endl;

  }

}

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

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

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

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

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;



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



int V;

vector<int> g[1010];

int match[1010];

bool use[1010];



bool dfs(int v){

  use[v] = true;

  for(int u : g[v]){

    int w = match[u];

    if(w<0 || (!use[w] && dfs(w))){

      match[u] = v;

      match[v] = u;

      return true;

    }

  }

  return false;

}



int bipartite_matching(){

  int res = 0;

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

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

    if(match[i]<0){

      memset(use,0,sizeof(use));

      if(dfs(i))res++;

    }

  }

  return res;

}



int main(){

  int m,n;

  while(cin >> m >> n){

    if(m==0 && n==0)break;

    V = m+n;

    rep(i,V)g[i].clear();



    vector<int> a(m),b(n);

    rep(i,m)cin >> a[i];

    rep(i,n)cin >> b[i];



    rep(i,m)rep(j,n){

      if(gcd(a[i],b[j])!=1){

	g[i].push_back(j+m);

	g[j+m].push_back(i);

      }

    }

   

    cout << bipartite_matching() << endl;

  }

}
// Slower C++ solution:
#include <stdio.h>

#include <vector>

using namespace std;

int n,k;int inline gcd(int a, int b) {while (b) {int c=a%b;a=b,b=c;} return a;}

vector<vector<int> >g;

vector<int>mt;

vector<char>used;

bool try_kuhn(int v) {

	if (used[v]) return false;

	used[v]=1;

	for (int i=g[v].size()-1;i>=0;i--) {

		int to=g[v][i];

		if (mt[to]==-1 || try_kuhn(mt[to])) {

			mt[to]=v;return true;

		}

	}

	return false;

}

int A[505],B[505];

int main() {

	int i,j;

	while (scanf("%d %d",&n,&k)!=EOF && (n || k)) {

		g.clear();mt.assign(k,-1);g.resize(n+k);

		for (i=0;i<n;scanf("%d",&A[i++]));

		for (i=0;i<k;scanf("%d",&B[i++]));

		for (i=0;i<n;i++) for (j=0;j<k;j++) if (gcd(A[i],B[j])>1) g[i].push_back(j);

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

			used.assign(n,false);

			try_kuhn(i);

		}

		for (i=0,j=0;i<k;i++) if (mt[i]!=-1) j++;

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

	}

	return 0;

}

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

#define N 505

int A[N],B[N],g[N][N],n,k,mt[N],used[N];

int inline gcd(int a, int b) {while (b) {int c=a%b;a=b,b=c;} return a;}

int kuhn(int v) {if (used[v]) return 0;used[v]=1;for (int i=g[v][0]-1;i;i--) {int to=g[v][i];if (mt[to]==-1 || kuhn(mt[to])) {mt[to]=v;return 1;}}return 0;}

int main() {

	int i,j;while (scanf("%d %d",&n,&k)!=EOF && (n || k)) {

		for (i=0;i<k;mt[i++]=-1);

		for (i=0;i<n;g[i][0]=1,scanf("%d",&A[i++]));for (i=0;i<k;scanf("%d",&B[i++]));

		for (i=0;i<n;i++) for (j=0;j<k;j++) if (gcd(A[i],B[j])>1) g[i][g[i][0]++]=j;

		for (i=0;i<n;i++) {for (j=0;j<n;used[j++]=0);kuhn(i);}

		for (i=0,j=0;i<k;j+=(mt[i]!=-1),i++);printf("%d\n",j);

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define pb       push_back

#define mp       make_pair

#define mod      1000000007

#define first    ff

#define second   ss

#define pi       acos(-1.0)

#define test     int t;cin>>t;while(t--)

typedef long long ll;

using namespace std;

vector<int>node[10001];

ll bigmod(ll a,ll b)

{

    ll  res=1;

    a=a%mod;

    if(a==0)

        return 0;

    while(b>0)

    {



           if(b%2)

            res=(res*a)%mod;

            b=b>>1;

            a=(a*a)%mod;

    }

    return res;

}

int main()

{      





     ios::sync_with_stdio(false);

     cin.tie(NULL);

     cout.tie(NULL);

     

     int n;

     cin>>n;



     ll ans=(bigmod(10,n)-(2*bigmod(9,n))%mod+bigmod(8,n))%mod;

     if(ans<0)

        cout<<ans+mod<<endl;

     else

     cout<<ans<<endl;



      return 0;

    

 }   

// Faster C++ solution for the same problem (measured speedup: 0.796638120030933x):
/*

* @Author: Kabid

* @Date:   {{create_time}}

* @Last Modified by:   Kabid

* @Last Modified time: 2020-09-20 20:58:29

*/

#include<bits/stdc++.h>

#include<cstdlib>

using namespace std;

#define ll long long

#define  in(x) scanf("%d",&x);

#define out(x) printf("%d",x);

#define  ins(x)  scanf("%s",x);

#define outs(x) printf("%s",x);

#define lin puts("");

#define _ putchar(' ');



int t;       //test cases

ll i, j;	 //iterators

ll n, k ,  q,  d, m, c, c1, c2, d1, x; //variables;

ll mx1 = LLONG_MIN, mx2 = LLONG_MIN, mx = LLONG_MIN, mn = LLONG_MAX;		// max min

char s[6], s1, s2;		// string

ll a [1000001], b [200001] ;

bool mox [1000001];	// array

map <int, int > mp;

vector <vector<ll>> vc;

vector <ll> v;

set <ll> st;

bool r;

ll p = 1000000007;

ll power(ll x, unsigned ll y, ll p)

{

	ll res = 1;     // Initialize result



	x = x % p; // Update x if it is more than or

	// equal to p



	if (x == 0) return 0; // In case x is divisible by p;



	while (y > 0)

	{

		// If y is odd, multiply x with result

		if (y & 1)

			res = (res * x) % p;



		// y must be even now

		y = y / 2; // y = y/2

		x = (x * x) % p;

	}

	return res;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	//cin >> t; q = t;

	t = 1;



	while (t--) {



		cin >> n;

		if (n == 1) {

			cout << 0 << endl;

			continue;

		}

		/*if (n == 2) {

			cout << 2 << endl;

			continue;

		}*/

		//ll ans=power(10,n-2,p);

		ll ans = 1;

		ll ans2 = 1;

		ll ans3 = 1;

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

			ans = ((ans ) * 10) % p;

			ans2 = (ans2 * 9) % p;

			ans3 = (ans3 * 8) % p;

		}

		//cout<<ans<<' '<<ans2<<' '<<ans3<<endl;



		cout << ((ans -2*ans2 +ans3)%p +p) %p<< endl;





		//cout<<mod;

	}





	return 0;



}
// Slower C++ solution:
#include<bits/stdc++.h>

#define pb       push_back

#define mp       make_pair

#define mod      1000000007

#define first    ff

#define second   ss

#define pi       acos(-1.0)

#define test     int t;cin>>t;while(t--)

typedef long long ll;

using namespace std;

vector<int>node[10001];

ll bigmod(ll a,ll b)

{

    ll  res=1;

    a=a%mod;

    if(a==0)

        return 0;

    while(b>0)

    {



           if(b%2)

            res=(res*a)%mod;

            b=b>>1;

            a=(a*a)%mod;

    }

    return res;

}

int main()

{      





     ios::sync_with_stdio(false);

     cin.tie(NULL);

     cout.tie(NULL);

     

     int n;

     cin>>n;



     ll ans=(bigmod(10,n)-(2*bigmod(9,n))%mod+bigmod(8,n))%mod;

     if(ans<0)

        cout<<ans+mod<<endl;

     else

     cout<<ans<<endl;



      return 0;

    

 }   

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

using namespace std;

#define ll long long

ll mod(ll n,ll m)

{

    ll ans=1;

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

    {

        ans=(ans*m)%1000000007;

    }

    return ans;

}

int main()

{

    ll n;cin>>n;

    ll ans=(((mod(n,10)-2*mod(n,9)+mod(n,8))%1000000007)+1000000007)%1000000007;

    cout<<ans<<endl;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring> 

#include <cmath>

#include <cstdio>

const long long mod=1e9+7;

using namespace std;

long long f(long long m,long long n){

	long long ans=1;

	while(n>0){

		if(n&1)

			ans=(ans*m)%mod;

		m=(m*m)%mod;

		n=(n/2)%mod;

	}

	return ans;

}

int main(){

	long long n;

	scanf("%lld",&n);	

		cout<<(f(10,n)%mod-(2*f(9,n))%mod+f(8,n)%mod+mod)%mod<<endl;	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.231135464704477x):
#include<algorithm>

#include<string>

#include<math.h>



using namespace std;



typedef long long ll;

const ll mod = 1e9 + 7;

ll N;



ll find(ll a,ll b){

	ll sum=1;

	while(b){

		if(b&1) sum=(sum*a)%mod;

		a=(a*a)%mod;

		b=b/2;

	}

	return sum;

}



int main(){

	scanf("%lld",&N);



	ll ans=find(10,N)-find(9,N)-find(9,N)+find(8,N);

	printf("%lld",(ans%mod+mod)%mod);



	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#include <math.h>

#include <iomanip>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF=1001001001;

const int mod=1e9+7;

int64_t dp[1000005][2][2];

int main() {

  int N;

  cin>>N;

  dp[0][0][0]=8,dp[0][1][0]=1,dp[0][0][1]=1;

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

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

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

        if(dp[i][j][k]==0){continue;}

        for(int next=0;next<=9;next++){

          if(next==0){

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

          }

          else if(next==9){

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

          }

          else{

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

          }

        }

      }

    }

  }

  //cout<<dp[1][0][1]<<endl;

  cout<<dp[N-1][1][1]<<endl;

  return 0;

}

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

using namespace std;

#include <math.h>

#include <iomanip>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF=1001001001;

const int mod=1e9+7;



int64_t N;

int64_t powmod(int64_t x){

  int64_t res=1;

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

    (res*=x)%=mod;

  }

  return res;

}

int main() {

  cin>>N;

  int64_t ans=powmod(10)-powmod(9)-powmod(9)+powmod(8);

  ans%=mod;

  ans=(ans+mod)%mod;

  cout<<ans<<endl;

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <utility>

#include <vector>

#include <string>



using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

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

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

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

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

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

const ll MOD = 1e9 + 7;

ll dp[1000001][2][2];



int main() {

    int N;

    cin >> N;

    dp[0][0][0] = 1;

    REP(i, N) REP(j, 2) REP(k, 2) REP(d, 10) {

        dp[i + 1][j || d == 0][k || d == 9] += dp[i][j][k];

        dp[i + 1][j || d == 0][k || d == 9] %= MOD;

    }

    cout << dp[N][1][1] << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.463615773219576x):
#include <iostream>

#include <algorithm>

#include <utility>

#include <vector>

#include <string>



using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

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

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

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

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

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

const ll MOD = 1e9 + 7;



ll power(int x, int y) {

    if (y == 0) return 0;

    if (y == 1) return x;

    ll p = power(x, y >> 1);

    if (y & 1) return p * p % MOD * x % MOD;

    else return p * p % MOD;

}



int main() {

    int N;

    cin >> N;

    ll ans = power(10, N) - 2 * power(9, N) + power(8, N);

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define lli long long

using namespace std;

lli mod=1e9+7;





lli black[100000+5];

lli white[100000+5];

vector<int>edge[100010];



void dpp(int v,int par)

{

   bool fl=0;

   white[v]=black[v]=1;

   for(int x:edge[v])

   {

     if(x==par)

     continue;

     fl=1;



     dpp(x,v);

     black[v]*=(white[x]);

     if(black[v]>=mod)

     black[v]%=mod;

     white[v]*=(white[x]+black[x]);

     if(white[v]>=mod)

     white[v]%=mod;



   }







}



int main()

{

   int n;

   cin>>n;



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

   {

     int a,b;

     cin>>a>>b;

     edge[a].push_back(b);

     edge[b].push_back(a);

   }

   dpp(1,-1);



   cout <<(white[1]+black[1])%mod;

}










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



using namespace std;

typedef long long int LL;

typedef long long int ll;

typedef pair<long long int, long long int> pii;

typedef pair<double, double> pdd;



#define SORT(c) sort((c).begin(),(c).end())

#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())

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

#define REP(i,n)  FOR(i,0,n)

#define SP << " " <<



LL mod = 1000000007;



pii solve(vector<vector<LL>> &graph, LL parent, LL idx)

{

  pii sum = {1,1};

  vector<pii> a;

  REP(i, graph[idx].size())

  {

    LL j = graph[idx][i];

    if (parent!=j)

    {

      a.push_back(solve(graph, idx, j));

    }

  }

  REP(i,a.size()){

    sum.first *= (a[i].first+a[i].second);

    sum.second *= a[i].first;

    sum.first %= mod;

    sum.second %= mod;

  }

  return sum;

}



int main()

{

  cin.tie(0);

  ios::sync_with_stdio(false);

  

  LL N;

  cin >> N;

  vector<vector<LL>> graph(N );



  REP(i, N - 1)

  {

    LL a, b;

    cin >> a >> b;

    a--;

    b--;

    graph[a].push_back(b);

    graph[b].push_back(a);

  }



  auto ans = solve(graph, -1, 0);

  cout << (ans.first + ans.second)%mod << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define N 100500

#define pb push_back

#define mp make_pair

#define fi first

#define se second

typedef long long ll;

const ll m = 1e9 + 7;

int n;

ll memo[N][5];

vector <int> adj[N];



ll mul(ll a , ll b) {

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

}



ll add(ll a , ll b) {

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

}



ll dp(int u , int color , int par) {

    ll &sol = memo[u][color];

    if (sol != -1) return sol;

    ll product = 1;

    for (int v : adj[u]) {

        if (v == par) continue;

        if (color == 0) {

            product = mul(product , add(dp(v , 0 , u) , dp(v , 1 , u)));

        } else {

            product = mul(product , dp(v , 0 , u));

        }

    }

    return sol = product;

}



int main() {

    scanf("%d" , &n);

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

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

        adj[u].pb(v);

        adj[v].pb(u);

    }

    memset (memo , -1 , sizeof memo);

    printf("%lld\n" , add(dp(1 , 0 , 1) , dp(1 , 1 , 1)));

}


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



using namespace std;

typedef long long int LL;

typedef long long int ll;

typedef pair<long long int, long long int> pii;

typedef pair<double, double> pdd;



#define SORT(c) sort((c).begin(),(c).end())

#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())

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

#define REP(i,n)  FOR(i,0,n)

#define SP << " " <<



LL mod = 1000000007;



pii solve(vector<vector<LL>> &graph, LL parent, LL idx)

{

  pii sum = {1,1};

  vector<pii> a;

  REP(i, graph[idx].size())

  {

    LL j = graph[idx][i];

    if (parent!=j)

    {

      a.push_back(solve(graph, idx, j));

    }

  }

  REP(i,a.size()){

    sum.first *= (a[i].first+a[i].second);

    sum.second *= a[i].first;

    sum.first %= mod;

    sum.second %= mod;

  }

  return sum;

}



int main()

{

  cin.tie(0);

  ios::sync_with_stdio(false);

  

  LL N;

  cin >> N;

  vector<vector<LL>> graph(N );



  REP(i, N - 1)

  {

    LL a, b;

    cin >> a >> b;

    a--;

    b--;

    graph[a].push_back(b);

    graph[b].push_back(a);

  }



  auto ans = solve(graph, -1, 0);

  cout << (ans.first + ans.second)%mod << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define lli long long

using namespace std;

lli mod=1e9+7;





lli black[100000+5];

lli white[100000+5];

vector<int>edge[100010];



void dpp(int v,int par)

{

   bool fl=0;

   white[v]=black[v]=1;

   for(int x:edge[v])

   {

     if(x==par)

     continue;

     fl=1;



     dpp(x,v);

     black[v]*=(white[x]);

     if(black[v]>=mod)

     black[v]%=mod;

     white[v]*=(white[x]+black[x]);

     if(white[v]>=mod)

     white[v]%=mod;



   }







}



int main()

{

   int n;

   cin>>n;



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

   {

     int a,b;

     cin>>a>>b;

     edge[a].push_back(b);

     edge[b].push_back(a);

   }

   dpp(1,-1);



   cout <<(white[1]+black[1])%mod;

}










// Faster C++ solution for the same problem (measured speedup: 3.4648695832275225x):
#include <iostream>

#include <vector>

#include <limits.h>

#include <algorithm>

#include <string>

#include <math.h>

#include <limits.h>

#include <queue>

#include <map>

#include <set>

#include <iomanip>

#include <bitset>

#include <cassert>

#include <random>

#include <functional>

#include <stack>

#include <iomanip>

using namespace std;

int MOD = 1e9 + 7;



int N;

typedef pair<int, int> pii;   //自分、親

vector<vector<int>> G;   //グラフ

vector<pii> order;



void setorder() {

	vector<bool> check;

	check.resize(N, false);   //来た->true

	queue<pii> st;

	st.push(pii(0,-1));

	while (!st.empty()) {

		pii cur = st.front();

		st.pop();

		check[cur.first] = true;

		order.push_back(cur);

		for (int next : G[cur.first]) {

			if (check[next])continue;

			st.push(pii(next, cur.first));

		}

	}

}



int main() {

	cin >> N;

	G.resize(N);

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

		int u, v;

		cin >> u >> v;

		G[--u].push_back(--v);

		G[v].push_back(u);

	}

	setorder();

	vector<long long> DP[2];

	DP[0].resize(N, 1);

	DP[1].resize(N, 1);

	for (int ord = N - 1; ord >= 0; ord--) {

		pii cur = order[ord];

		//葉っぱの場合

		if (G[cur.first].size() == 1 && G[cur.first][0] == cur.second) {

			DP[0][cur.first] = 1;

			DP[1][cur.first] = 1;

		}

		if (cur.second == -1)continue;

		DP[0][cur.second] *= (DP[0][cur.first]+DP[1][cur.first]);

		DP[1][cur.second] *= (DP[0][cur.first]);

		DP[0][cur.second] %= MOD;

		DP[1][cur.second] %= MOD;

	}

	cout << (DP[0][0] + DP[1][0]) % MOD << endl;

	return 0;

}