该国有 n 个城市和 n - 1 条双向道路,如果仅沿着道路移动,则可以从每个城市到达任何其他城市。城市用 1 到 n 之间的整数进行编号。
所有道路最初都不好,但政府希望改善一些道路的状况。我们假设,如果从城市 x 的首都到任何其他城市的路径至多包含一条糟糕的道路,那么公民对道路的改善感到高兴。
你的任务是 — 对于每一种可能的 x 确定提高某些道路质量的方法数量,以满足公民的状况。由于这些值可能相当大,因此您需要打印每个值模 1 000 000 007 (109 + 7)。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 2·105) — 该国城市的数量。下一行包含 n - 1 个正整数 p2, p3, p4, ..., pn (1 ≤ pi ≤ i - 1) — 国家/地区道路的描述。数字pi表示该国有一条道路连接城市pi和城市i。
输出
打印 n 个整数 a1, a2, ..., an,其中 ai 是改善道路质量的方法的数量,模 1 000 000 007 (109 + 7),如果该国的首都位于城市 i。
示例
输入 #1
3 1 1
输出 #1
4 3 3
输入 #2
5 1 2 3 4
输出 #2
5 8 9 8 5