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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\n\nclass Graph:\n    def __init__(self, n_vertices, edges, directed=True, weighted=False):\n        self.n_vertices = n_vertices\n        self.edges = edges\n        self.directed = directed\n        self.weighted = weighted\n\n    @property\n    def adj(self):\n        try:\n            return self._adj\n        except AttributeError:\n            adj = [[] for _ in range(self.n_vertices)]\n            def d_w(e):\n                adj[e[0]].append((e[1],e[2]))\n            def ud_w(e):\n                adj[e[0]].append((e[1],e[2]))\n                adj[e[1]].append((e[0],e[2]))\n            def d_uw(e):\n                adj[e[0]].append(e[1])\n            def ud_uw(e):\n                adj[e[0]].append(e[1])\n                adj[e[1]].append(e[0])\n            helper = (ud_uw, d_uw, ud_w, d_w)[self.directed+self.weighted*2]\n            for e in self.edges:\n                helper(e)\n            self._adj = adj\n            return adj\n\nclass RootedTree(Graph):\n    def __init__(self, n_vertices, edges, root_vertex):\n        self.root = root_vertex\n        super().__init__(n_vertices, edges, False, False)\n\n    @property\n    def parent(self):\n        try:\n            return self._parent\n        except AttributeError:\n            adj = self.adj\n            parent = [None]*self.n_vertices\n            parent[self.root] = -1\n            stack = [self.root]\n            for i in range(self.n_vertices):\n                v = stack.pop()\n                for u in adj[v]:\n                    if parent[u] is None:\n                        parent[u] = v\n                        stack.append(u)\n            self._parent = parent\n            return parent\n\n    @property\n    def children(self):\n        try:\n            return self._children\n        except AttributeError:\n            children = [None]*self.n_vertices\n            for v,(l,p) in enumerate(zip(self.adj,self.parent)):\n                children[v] = [u for u in l if u != p]\n            self._children = children\n            return children\n\n    @property\n    def dfs_order(self):\n        try:\n            return self._dfs_order\n        except AttributeError:\n            order = [None]*self.n_vertices\n            children = self.children\n            stack = [self.root]\n            for i in range(self.n_vertices):\n                v = stack.pop()\n                order[i] = v\n                for u in children[v]:\n                    stack.append(u)\n            self._dfs_order = order\n            return order\n\nfrom functools import reduce\nfrom itertools import accumulate,chain\ndef rerooting(rooted_tree, merge, identity, finalize):\n    N = rooted_tree.n_vertices\n    parent = rooted_tree.parent\n    children = rooted_tree.children\n    order = rooted_tree.dfs_order\n\n    # from leaf to parent\n    dp_down = [None]*N\n    for v in reversed(order[1:]):\n        dp_down[v] = finalize(reduce(merge,\n            (dp_down[c] for c in children[v]),\n            identity))\n\n    # from parent to leaf\n    dp_up = [None]*N\n    dp_up[0] = identity\n    for v in order:\n        if len(children[v]) == 0:\n            continue\n        temp = (dp_up[v],)+tuple(dp_down[u] for u in children[v])+(identity,)\n        left = accumulate(temp[:-2],merge)\n        right = tuple(accumulate(reversed(temp[2:]),merge))\n        for u,l,r in zip(children[v],left,reversed(right)):\n            dp_up[u] = finalize(merge(l,r))\n\n    res = [None]*N\n    for v,l in enumerate(children):\n        res[v] = reduce(merge,\n                    (dp_down[u] for u in children[v]),\n                    identity)\n        res[v] = finalize(merge(res[v], dp_up[v]))\n\n    return res\n\ndef solve(T):\n    MOD = 10**9 + 7\n    def merge(x,y):\n        return (x*y)%MOD\n    def finalize(x):\n        return x+1\n\n    return [v-1 for v in rerooting(T,merge,1,finalize)]\n\n\ndef __starting_point():\n    N = int(input())\n    edges = [(i+1,p-1) for i,p in enumerate(map(int,input().split()))]\n    T = RootedTree(N, edges, 0)\n    print(*solve(T))\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 20429