Problem:
 Score : 100 points    Problem Statement There is a tree with N vertices, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq N - 1 ), the i -th edge connects Vertex x_i and y_i .  Taro has decided to paint each vertex in white or black.
Here, it is not allowed to paint two adjacent vertices both in black.  Find the number of ways in which the vertices can be painted, modulo 10^9 + 7 .      Constraints  All values in input are integers.  1 \leq N \leq 10^5  1 \leq x_i, y_i \leq N  The given graph is a tree.         Input Input is given from Standard Input in the following format:  N  x_1  y_1  x_2  y_2  :  x_{N - 1}  y_{N - 1}       Output Print the number of ways in which the vertices can be painted, modulo 10^9 + 7 .        Sample Input 1 3
1 2
2 3      Sample Output 1 5  There are five ways to paint the vertices, as follows:        Sample Input 2 4
1 2
1 3
1 4      Sample Output 2 9  There are nine ways to paint the vertices, as follows:        Sample Input 3 1      Sample Output 3 2       Sample Input 4 10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7      Sample Output 4 157

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()













import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

show_flg=False
show_flg=True

ans=0
n=I()
if n==1:print(2);exit()
tr=Tree(n)
v,root=tr.dfs2(0)
p=tr.parent(0)
x=[[1,1]for i in range(n)]
for c in root[::-1]:
        
    x[p[c]][0]*=sum(x[c])
    x[p[c]][1]*=x[c][0]
    x[p[c]][0]%=mo
    x[p[c]][1]%=mo
    
print(sum(x[0])%mo)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]
mod = 10**9 + 7

for i in range(n-1):
    for j in range(2):
        C[i][j] -= 1

ans = 0
M = [[] for i in range(n)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

D = [[1,1] for i in range(n)]
MN = [len(M[i]) for i in range(n)]


V = [0] * n
Q = []
for i in range(1, n):
    if MN[i] == 1:
        Q.append(i)
        V[i] = 1



s = 0
while s < len(Q):
    x = Q[s]
    for y in M[x]:
        if V[y] == 0:
            
            D[y][0] = (D[y][0] * sum(D[x])) % mod
            D[y][1] = (D[y][1] * D[x][0]) % mod
            MN[y] -= 1
            if (y != 0 and MN[y] == 1) or (y == 0 and MN[y] == 0):
                V[y] = 1
                Q.append(y)
    s += 1

print(sum(D[0]) % mod)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
inp = sys.stdin.buffer.readline


def resolve():
    MOD = 10 ** 9 + 7

    
    def dfs(v, parent):
        vistied[v] = True
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent or vistied[to]:
                continue
            dfs(to, v)
            
            
            dp[v][0] *= (dp[to][0] + dp[to][1]) % MOD
            dp[v][1] *= dp[to][0] % MOD

    N = int(inp())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        G[x].append(y)
        G[y].append(x)
    dp = [[0] * 2 for _ in range(N)]
    vistied = [False] * N

    dfs(0, -1)
    ans = dp[0][0] + dp[0][1]
    print(ans % MOD)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from collections import deque
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


def make_tree_0index(N):
    edge_dic = {}
    for _ in range(N-1):
        x, y = na()
        x -= 1
        y -= 1
        if x in edge_dic:
            edge_dic[x].append(y)
        else:
            edge_dic[x] = [y]
        if y in edge_dic:
            edge_dic[y].append(x)
        else:
            edge_dic[y] = [x]
    return edge_dic


N = ni()
if N == 1:
    print(2)
    exit()
edge_dic = make_tree_0index(N)
ans = [[0] * 2 for _ in range(N)]
mod = 10 ** 9 + 7

parent_array = [-2] * N
parent_array[0] = -1
node1 = deque([0])
node2 = deque([0])

while(len(node1)):
    n = node1.popleft()
    for v in edge_dic[n]:
        if parent_array[v] == -2:
            parent_array[v] = n
            node1.append(v)
            node2.append(v)

while(len(node2)):
    n = node2.pop()
    white = 1
    black = 1
    for v in edge_dic[n]:
        if parent_array[n] == v:
            continue
        white = (white * (ans[v][0] + ans[v][1])) % mod
        black = black * ans[v][0] % mod
    ans[n][0] = white
    ans[n][1] = black


print((ans[0][0] + ans[0][1]) % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

MOD = 10 ** 9 + 7
def dfs(v, pv):
    white, black = 1, 1
    for nv in edge[v]:
        if nv == pv: continue
        rw, rb = dfs(nv, v)
        white *= rw + rb
        white %= MOD
        black *= rw
        black %= MOD
    return white, black

N = int(input())
edge = [[] for _ in range(N)]

for i in range(N-1):
    x, y = map(lambda x:int(x)-1, input().split())
    edge[x].append(y)
    edge[y].append(x)

print(sum(dfs(0, -1)) % MOD)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
xy = [LIST() for _ in range(N-1)]
tree = [[] for _ in range(N)]
for x, y in xy:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

def rec(n, par):
    f, g = 1, 1
    for node in tree[n]:
        if node == par:
            continue
        fn, gn = rec(node, n)
        f *= gn
        f %= mod
        g *= fn
        g %= mod
 
    return (f+g)%mod, g
 
print(rec(0, None)[0])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
xy = [LIST() for _ in range(N-1)]
tree = [[] for _ in range(N)]
for x, y in xy:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

@lru_cache(maxsize=None)
def DFS(i, par, c):  
    if par and len(tree[i]) == 1:
        return 1
    if c == 0:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= (DFS(node, i, 0) + DFS(node, i, 1))
                cnt %= mod
        return cnt
    elif c == 1:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= DFS(node, i, 0)
                cnt %= mod
        return cnt

ans = DFS(0, None, 0)+DFS(0, None, 1)
print(ans%mod)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ns = [[] for _ in range(n)]
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)

d1 = [None]*n
d2 = [None]*n
M = 10**9+7
def sub(u, p):
    if d1[u] is not None:
        return d1[u], d2[u]
    v1 = 1 
    v2 = 1 
    for v in ns[u]:
        if v==p:
            continue
        w1, w2 = sub(v, u)
        v1 *= (w1+w2)
        v2 *= w1
        v1 %= M
        v2 %= M
    d1[u] = v1
    d2[u] = v2
    return v1, v2
sub(0, -1)
print((d1[0]+d2[0])%M)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def memodp(DPW, DPB, near, x, FLAG):
    if DPW[x] + DPB[x] > 2:
        return (DPB[x] + DPW[x]) % mod
    else:
        for i in near[x]:
            if i not in FLAG:
                FLAG.add(i)
                DPW[x] *= memodp(DPW, DPB, near, i, FLAG)
                DPB[x] *= DPW[i]
        DPW[x], DPB[x] = DPW[x] % mod, DPB[x] % mod
        return (DPW[x] + DPB[x]) % mod


n = int(input())
xy = [list(map(int, input().split())) for i in range(n - 1)]

near = [[] for _ in range(n)]
for x, y in xy:
    near[x - 1].append(y - 1)
    near[y - 1].append(x - 1)

dpw, dpb, flag = [1] * n, [1] * n, set([0])
print(memodp(dpw, dpb, near, 0, flag))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def memodp(DPW, DPB, near, x, FLAG):
    if DPW[x] + DPB[x] > 2:
        return (DPB[x] + DPW[x]) % mod
    else:
        for i in near[x]:
            if i not in FLAG:
                FLAG.add(i)
                DPW[x] *= memodp(DPW, DPB, near, i, FLAG)
                DPB[x] *= DPW[i]
        DPW[x], DPB[x] = DPW[x] % mod, DPB[x] % mod
        return (DPW[x] + DPB[x]) % mod


n = int(input())
xy = [list(map(int, input().split())) for i in range(n - 1)]

near = [[] for _ in range(n)]
for x, y in xy:
    near[x - 1].append(y - 1)
    near[y - 1].append(x - 1)

dpw, dpb, flag = [1] * n, [1] * n, set([0])
print(memodp(dpw, dpb, near, 0, flag) % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

N = int(input())
MOD = 10**9+7
G = [set() for _ in range(N)]
for i in range(N-1):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].add(y)
    G[y].add(x)

def dfs(v, r):
    w, b = 1, 1
    for u in G[v]:
        if u == r: continue
        c_w, c_b = dfs(u, v)
        w *= c_w + c_b
        b *= c_w
    w %= MOD
    b %= MOD
    return w, b

print(sum(dfs(0, None))%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

N = int(input())
MOD = 10**9+7
G = [[] for _ in range(N)]
for i in range(N-1):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)
    G[y].append(x)

def dfs(v, r):
    w, b = 1, 1
    for u in G[v]:
        if u == r: continue
        c_w, c_b = dfs(u, v)
        w *= c_w + c_b
        b *= c_w
    w %= MOD
    b %= MOD
    return w, b

print(sum(dfs(0, None))%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

N = int(input())
MOD = 10**9+7
G = [[] for _ in range(N)]
for i in range(N-1):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)
    G[y].append(x)

def dfs(v, r):
    w, b = 1, 1
    for u in G[v]:
        if u == r: continue
        c_w, c_b = dfs(u, v)
        w *= c_w + c_b
        b *= c_w
    w %= MOD
    b %= MOD
    return w, b

print(sum(dfs(0, None))%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
MOD = 1_000_000_007
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N - 1):
    x, y = list(map(int, input().split()))
    G[x].append(y)
    G[y].append(x)

def dfs(v, root):
    w, b = 1, 1
    for u in G[v]:
        if u == root:
            continue
        child_w, child_b = dfs(u ,v)
        w *= child_w + child_b
        b *= child_w
    w %= MOD
    b %= MOD
    return w, b

print(sum(dfs(1, None)) % MOD)

Solution (Python):






import sys
input = sys.stdin.readline


import heapq 
import copy
import math
import decimal

















def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))



def pr_list(a):
	print(*a, sep=" ")
def main():
	
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	start = {}
	def pre_sum(arr):
		ans = [arr[0]]
		for i in range(1,len(arr)):
			ans.append(ans[-1]+ arr[i])
		return ans
	for test in range(tests):
		n = inp()
		branch = {}

		
		for i in range(n-1):
			[p,r] =  inlt()
			if p in branch:
				branch[p].append(r)
			else:
				branch[p] = [r]
			if r in branch:
				branch[r].append(p)
			else:
				branch[r] = [p]
		parent = [-1 for i in range(n+1)]
		
		
		

		dp = [[0 for j in range(n+1)] for i in range(2)]
		leaf = {}
		ans = 2
		stack = [1]
		parent[1] = 0
		if n == 1:
			print(2)
			continue
		while(stack!=[]):
			
			curr = stack[-1]
			flag = 0
			for i in branch[curr]:
				if parent[i] == -1:
					parent[i] = curr
					stack.append(i)
					flag = 1
			if flag == 0:
				curr= stack.pop()
				white = 1
				black = 1
				for i in branch[curr]:
					if i !=parent[curr]:
						white = (white*(dp[0][i] + dp[1][i]))%mod
						black = (black*(dp[0][i]))%mod
				dp[0][curr] = white
				dp[1][curr] = black

		print((dp[0][1] + dp[1][1])%mod) 


		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
				
		
		
		
		
		
		
		
		




		


if __name__== "__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
adj=[[] for i in range(n+1)]
dp=[[-1,-1] for i in range(n+1)]
mod=10**9 +7
def dfs(node,parent,color):
    if dp[node][color]!=-1:
        return dp[node][color]
    count=1
    if color==0:
        for i in adj[node]:
            if i==parent:
                continue
            temp=(dfs(i,node,0)+dfs(i,node,1))%mod
            count=(count*temp)%mod
    else:
        for i in adj[node]:
            if i==parent:
                continue
            temp=dfs(i,node,0)%mod
            count=(count*temp)%mod
    dp[node][color]=count
    return count
for _ in range(n-1):
    u,v=map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
print((dfs(1,-1,0)+dfs(1,-1,1))%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

n = int(input())
e = [[] for i in range(n+1)]
mod = 10**9+7

for i in range(n-1):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)

def dfs(x,bef):
    w = 1
    b = 1
    for nex in e[x]:
        if nex == bef:
            continue
        nw,nb = dfs(nex,x)
        w *= (nw+nb)%mod
        b *= nw%mod
        w %= mod
        b %= mod
    return w,b

a,b = dfs(1,-1)
print((a+b)%mod)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**6)

MOD = 10**9 + 7

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

def dfs(pos: int, par: int):
    
    
    white = 1
    black = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            white *= sum(tmp)
            black *= tmp[0]
            white %= MOD
            black %= MOD
    return [white, black]  

print(sum(dfs(0, 0))%MOD)

Solution (Python):
import sys
from collections import defaultdict


sys.setrecursionlimit(10 ** 6)


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        y -= 1
        adj_nodes[x].append(y)
        adj_nodes[y].append(x)
    dp_b = [0 for _ in range(N)]
    dp_w = [0 for _ in range(N)]

    def bfs(node, parent):
        black = 1
        white = 1
        for child in adj_nodes[node]:
            if child == parent:
                continue
            bfs(child, node)
            black *= dp_w[child]
            white *= dp_b[child] + dp_w[child]
            black %= MOD
            white %= MOD
        dp_b[node] = black
        dp_w[node] = white

    bfs(0, None)
    print((dp_b[0] + dp_w[0]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[node][BLACK] = product(OPT[child[i]][WHITE])
    OPT[node][WHITE] = product(OPT[child[i]][WHITE|BLACK])
    """
    N = read_int()
    G = [[] for _ in range(N)]
    modulo = 10**9+7
    for _ in range(N-1):
        x, y = read_ints()
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    
    VISIT, CALCULATE = 0, 1
    BLACK, WHITE = 0, 1
    OPT = [
        [1, 1] for _ in range(N)
    ]
    Q = [(VISIT, 0, None)]
    while len(Q) != 0:
        t, node, parent = Q.pop()
        if VISIT == t:
            Q.append((CALCULATE, node, parent))
            for child in G[node]:
                if child != parent:
                    Q.append((VISIT, child, node))
        else:
            for child in G[node]:
                if child != parent:
                    OPT[node][BLACK] = (OPT[node][BLACK]*OPT[child][WHITE])%modulo
                    OPT[node][WHITE] = (OPT[node][WHITE]*(OPT[child][WHITE]+OPT[child][BLACK]))%modulo
    return (OPT[0][BLACK]+OPT[0][WHITE])%modulo


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
mod=10**9+7
def independent_set(n,graph):

	ways=[[0]*2 for _ in  range(n)]
	
	

	def dfs(node,parent):
		
		
		

		w_w=b_w=1

		for i in graph[node]:
			if i!=parent:
				dfs(i,node)	
				w_w=w_w*sum(ways[i])%mod
				b_w=b_w*ways[i][0]%mod
		ways[node][0]=w_w
		ways[node][1]=b_w

	dfs(0,-1)
	
	return (ways[0][0]+ways[0][1])%mod


n=int(input())
graph={i:[] for i in range(n)}

for i in range(n-1):
	u,v=map(lambda x:int(x)-1,input().split())
	graph[u].append(v)
	graph[v].append(u)


res=independent_set(n,graph)


print(res%(10**9+7))

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

N, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)
    E[y].append(x)

def dfs(cur, par):
    w, b = 1, 1
    for nxt in E[cur]:
        if nxt == par:
            continue
        ww, bb = dfs(nxt, cur)
        w = (w * (ww + bb)) % mod
        b = (b * ww) % mod
    return (w, b)

print(sum(dfs(1, -1)) % mod)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  T[x].append(y)
  T[y].append(x)
dp = [[-1]*n for _ in range(2)]
def dfs(color, i, par=-1):
  if dp[color][i] != -1:
    return dp[color][i]
  res = 1
  if color == 0:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i) + dfs(1, v, i)
      res %= MOD
  else:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i)
      res %= MOD
  dp[color][i] = res
  return res
ans = dfs(0, 0) + dfs(1, 0)
ans %= MOD
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

N = int(input())
T = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int1, input().split())
    T[a].append(b)
    T[b].append(a)


def dfs(x, parent):
    b, w = 1, 1
    for n in T[x]:
        if n == parent:
            continue
        nb, nw = dfs(n, x)
        b *= nw
        w *= (nw + nb)
    b %= MOD
    w %= MOD
    return b, w


b, w = dfs(0, 0)
print((b + w) % MOD)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    XY=[tuple(map(int,input().split())) for i in range(n-1)]
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
        graph[y-1].append(x-1)
    queue=deque([0])
    visited=[False]*n
    use=[False]*n
    
    dp=[[0,0] for _ in range(n)]
    mod=10**9+7
    while queue:
        node=queue[-1] 
        if not visited[node]:
            visited[node]=True
            for xnode in graph[node]:
                if visited[xnode]:continue
                queue.append(xnode)
        else:
            queue.pop()
            b,w=1,1
            for xnode in graph[node]:   
                if use[xnode]:
                    w=w*(dp[xnode][0]+dp[xnode][1])%mod
                    b=b*dp[xnode][0]%mod 
            dp[node][0]=w%mod
            dp[node][1]=b%mod 
            use[node]=True
    print(sum(dp[0])%mod)

if __name__=='__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n=int(input())
mod=10**9+7
l=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    l[a].append(b)
    l[b].append(a)
def dp(x,par):
    res_w,res_t=1,1
    for y in l[x]:
        if y==par:
            continue
        w,t=dp(y,x)
        res_w=(res_w*w)%mod
        res_t=(res_t*t)%mod
    w,t=res_t,(res_t+res_w)%mod
    return w,t
print(dp(1,0)[1])

Solution (Python):
from collections import deque

n = int(input())
mod = 10 ** 9 + 7
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

start = 1

que = deque([1])
par = [-1] * (n + 1)
topo = []
while que:
    v = que.popleft()
    topo.append(v)
    for u in graph[v]:
        if par[v] == u:
            continue
        par[u] = v
        que.append(u)

dpb = [0] * (n + 1)
dpw = [0] * (n + 1)

for i in topo[::-1]:
    dpb[i] = 1
    dpw[i] = 1
    for j in graph[i]:
        if j == par[i]:
            continue
        dpb[i] *= dpw[j]
        dpw[i] *= dpb[j] + dpw[j]
    dpw[i] %= mod
    dpb[i] %= mod

print((dpw[1] + dpb[1]) % mod)