当地的丛林正被猴子占领！树木正在迅速被它们殖民！作为一名勇敢的猿类照片收集者，这是你拍摄如此多灵长类动物照片的绝佳机会，这肯定会让你的同事们大吃一惊。

具体来说，每天都会有一只新猴子发现你最喜欢的那棵拥有 $n$ 个树枝的树。根据你长期观察灵长类动物的经验，你了解两件事。第一，树上的每个树枝只能容纳一只猴子。第二，猴子是非常具有社交性的动物，它们总是成群结队地呆在一起，也就是说，它们占领的树枝形成一个单一的连通分量。

这种特殊的入侵猴子物种对你来说是全新的，你还没有学会如何区分它们。尽管如此，你仍然想知道：在树被猴子填满之前，你每天可以拍到多少种不同的猴群照片？

作为一个例子，考虑第一个样例，如图 J.1 所示。在第三天，你可以拍到四种不同的猴群照片。

图 J.1：第三天第一个样例的直观展示。如果树枝重叠，则它们是相连的（注意树枝 1 和 2 之间，以及树枝 3 和 4 之间的微小间隙）。猴子图片来自 freevector.com。

给定你最喜欢的树的精确结构，请确定从第 $1$ 天到第 $n$ 天，猴子在当天可能占领的不同树枝集合的数量，模 $10^9 + 7$。

输入格式

输入包含：

• 一行，包含一个整数 $n$ ($1 \le n \le 1000$)，表示树中的树枝数量。
• $n-1$ 行，其中第 $i$ 行（$1 \le i \le n-1$）包含一个整数 $p_i$ ($0 \le p_i < i$)，表示树枝 $i$ 与树枝 $p_i$ 的上端相连。

树枝的编号从 $0$ 到 $n - 1$（闭区间）。树枝 $0$ 与树根相连，也可以容纳一只猴子。

输出格式

输出 $n$ 个整数。第 $k$ 个整数应为由恰好 $k$ 个树枝组成的连通子树的数量，模 $10^9 + 7$。

样例

样例输入 1

5
0
0
1
1

样例输出 1

5
4
4
3
1

样例输入 2

3
0
1

样例输出 2

3
2
1