The country has n cities and n - 1 bidirectional roads, it is possible to get from every city to any other one if you move only along the roads. The cities are numbered with integers from 1 to n inclusive.

All the roads are initially bad, but the government wants to improve the state of some roads. We will assume that the citizens are happy about road improvement if the path from the capital located in city x to any other city contains at most one bad road.

Your task is — for every possible x determine the number of ways of improving the quality of some roads in order to meet the citizens' condition. As those values can be rather large, you need to print each value modulo 1 000 000 007 (10^9 + 7).


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 2·10^5) — the number of cities in the country. Next line contains n - 1 positive integers p_2, p_3, p_4, ..., p_{n} (1 ≤ p_{i} ≤ i - 1) — the description of the roads in the country. Number p_{i} means that the country has a road connecting city p_{i} and city i. 


-----Output-----

Print n integers a_1, a_2, ..., a_{n}, where a_{i} is the sought number of ways to improve the quality of the roads modulo 1 000 000 007 (10^9 + 7), if the capital of the country is at city number i.


-----Examples-----
Input
3
1 1

Output
4 3 3
Input
5
1 2 3 4

Output
5 8 9 8 5

Difficulty: competition

Starter code:

Solutions:


class Graph:
    def __init__(self, n_vertices, edges, directed=True, weighted=False):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed
        self.weighted = weighted

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            def d_w(e):
                adj[e[0]].append((e[1],e[2]))
            def ud_w(e):
                adj[e[0]].append((e[1],e[2]))
                adj[e[1]].append((e[0],e[2]))
            def d_uw(e):
                adj[e[0]].append(e[1])
            def ud_uw(e):
                adj[e[0]].append(e[1])
                adj[e[1]].append(e[0])
            helper = (ud_uw, d_uw, ud_w, d_w)[self.directed+self.weighted*2]
            for e in self.edges:
                helper(e)
            self._adj = adj
            return adj

class RootedTree(Graph):
    def __init__(self, n_vertices, edges, root_vertex):
        self.root = root_vertex
        super().__init__(n_vertices, edges, False, False)

    @property
    def parent(self):
        try:
            return self._parent
        except AttributeError:
            adj = self.adj
            parent = [None]*self.n_vertices
            parent[self.root] = -1
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                for u in adj[v]:
                    if parent[u] is None:
                        parent[u] = v
                        stack.append(u)
            self._parent = parent
            return parent

    @property
    def children(self):
        try:
            return self._children
        except AttributeError:
            children = [None]*self.n_vertices
            for v,(l,p) in enumerate(zip(self.adj,self.parent)):
                children[v] = [u for u in l if u != p]
            self._children = children
            return children

    @property
    def dfs_order(self):
        try:
            return self._dfs_order
        except AttributeError:
            order = [None]*self.n_vertices
            children = self.children
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                order[i] = v
                for u in children[v]:
                    stack.append(u)
            self._dfs_order = order
            return order

from functools import reduce
from itertools import accumulate,chain
def rerooting(rooted_tree, merge, identity, finalize):
    N = rooted_tree.n_vertices
    parent = rooted_tree.parent
    children = rooted_tree.children
    order = rooted_tree.dfs_order

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order[1:]):
        dp_down[v] = finalize(reduce(merge,
            (dp_down[c] for c in children[v]),
            identity))

    # from parent to leaf
    dp_up = [None]*N
    dp_up[0] = identity
    for v in order:
        if len(children[v]) == 0:
            continue
        temp = (dp_up[v],)+tuple(dp_down[u] for u in children[v])+(identity,)
        left = tuple(accumulate(temp,merge))
        right = tuple(accumulate(reversed(temp[2:]),merge))
        for u,l,r in zip(children[v],left,reversed(right)):
            dp_up[u] = finalize(merge(l,r))

    res = [None]*N
    for v,l in enumerate(children):
        res[v] = reduce(merge,
                    (dp_down[u] for u in children[v]),
                    identity)
        res[v] = finalize(merge(res[v], dp_up[v]))

    return res

def solve(T):
    MOD = 10**9 + 7
    def merge(x,y):
        return (x*y)%MOD
    def finalize(x):
        return x+1

    return [v-1 for v in rerooting(T,merge,1,finalize)]


def __starting_point():
    N = int(input())
    edges = [(i+1,p-1) for i,p in enumerate(map(int,input().split()))]
    T = RootedTree(N, edges, 0)
    print(*solve(T))

__starting_point()



class Graph:
    def __init__(self, n_vertices, edges, directed=True, weighted=False):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed
        self.weighted = weighted

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            def d_w(e):
                adj[e[0]].append((e[1],e[2]))
            def ud_w(e):
                adj[e[0]].append((e[1],e[2]))
                adj[e[1]].append((e[0],e[2]))
            def d_uw(e):
                adj[e[0]].append(e[1])
            def ud_uw(e):
                adj[e[0]].append(e[1])
                adj[e[1]].append(e[0])
            helper = (ud_uw, d_uw, ud_w, d_w)[self.directed+self.weighted*2]
            for e in self.edges:
                helper(e)
            self._adj = adj
            return adj

class RootedTree(Graph):
    def __init__(self, n_vertices, edges, root_vertex):
        self.root = root_vertex
        super().__init__(n_vertices, edges, False, False)

    @property
    def parent(self):
        try:
            return self._parent
        except AttributeError:
            adj = self.adj
            parent = [None]*self.n_vertices
            parent[self.root] = -1
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                for u in adj[v]:
                    if parent[u] is None:
                        parent[u] = v
                        stack.append(u)
            self._parent = parent
            return parent

    @property
    def children(self):
        try:
            return self._children
        except AttributeError:
            children = [None]*self.n_vertices
            for v,(l,p) in enumerate(zip(self.adj,self.parent)):
                children[v] = [u for u in l if u != p]
            self._children = children
            return children

    @property
    def dfs_order(self):
        try:
            return self._dfs_order
        except AttributeError:
            order = [None]*self.n_vertices
            children = self.children
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                order[i] = v
                for u in children[v]:
                    stack.append(u)
            self._dfs_order = order
            return order

from functools import reduce
from itertools import accumulate,chain
def rerooting(rooted_tree, merge, identity, finalize):
    N = rooted_tree.n_vertices
    parent = rooted_tree.parent
    children = rooted_tree.children
    order = rooted_tree.dfs_order

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order[1:]):
        dp_down[v] = finalize(reduce(merge,
            (dp_down[c] for c in children[v]),
            identity))

    # from parent to leaf
    dp_up = [None]*N
    dp_up[0] = identity
    for v in order:
        if len(children[v]) == 0:
            continue
        temp = (dp_up[v],)+tuple(dp_down[u] for u in children[v])+(identity,)
        left = accumulate(temp[:-2],merge)
        right = tuple(accumulate(reversed(temp[2:]),merge))
        for u,l,r in zip(children[v],left,reversed(right)):
            dp_up[u] = finalize(merge(l,r))

    res = [None]*N
    for v,l in enumerate(children):
        res[v] = reduce(merge,
                    (dp_down[u] for u in children[v]),
                    identity)
        res[v] = finalize(merge(res[v], dp_up[v]))

    return res

def solve(T):
    MOD = 10**9 + 7
    def merge(x,y):
        return (x*y)%MOD
    def finalize(x):
        return x+1

    return [v-1 for v in rerooting(T,merge,1,finalize)]


def __starting_point():
    N = int(input())
    edges = [(i+1,p-1) for i,p in enumerate(map(int,input().split()))]
    T = RootedTree(N, edges, 0)
    print(*solve(T))

__starting_point()