정글 작업

지역 정글이 원숭이들에게 점령당하고 있다! 나무들도 빠르게 원숭이들의 서식지가 되고 있다! 브레이브 에이프 픽처스의 사진작가로서, 동료들을 틀림없이 놀라게 할 영장류 사진을 아주 많이 찍을 기회가 왔다.

특히 매일 새로운 원숭이 한 마리가 $n$ 개의 가지로 이루어진 당신의 가장 좋아하는 나무를 발견한다. 오랜 기간 영장류를 관찰한 경험으로 두 가지를 알고 있다. 첫째, 나무의 각 가지에는 원숭이 한 마리만 들어갈 수 있다. 둘째, 원숭이는 사회성이 매우 강한 동물이라 항상 무리를 지어 다니며, 즉 원숭이가 차지하는 가지들은 하나의 연결 성분을 이룬다.

이 침입종 원숭이는 당신에게 처음이라 서로를 구별하는 방법을 아직 알지 못한다. 그래도 매일 나무가 원숭이로 가득 찰 때까지, 원숭이 무리의 서로 다른 사진을 몇 장이나 찍을 수 있을지 궁금하다.

예를 들어 그림 J.1에 나타난 첫 번째 샘플 케이스를 보자. 3일째에는 원숭이 무리의 사진을 네 가지 방식으로 찍을 수 있다.

그림 J.1: 3일째 첫 번째 샘플 케이스의 시각화. 가지끼리 겹치면 연결된 것으로 본다(가지 1과 2 사이, 그리고 가지 3과 4 사이에 작은 틈이 있음에 주의).

원숭이 이미지 출처: freevector.com

당신이 좋아하는 나무의 정확한 구조가 주어질 때, 1일부터 $n$일까지 각 날에 원숭이들이 차지할 수 있는 서로 다른 가지 집합의 개수를 $10^9+7$로 나눈 나머지로 구하라.

입력은 다음과 같이 주어진다.

• 첫 번째 줄에 정수 $n$ ($1 \leq n \leq 1000$)이 주어진다. 나무의 가지 개수이다.
• 이어서 $n-1$개의 줄이 주어진다. $i$번째 줄 ($1 \leq i \leq n-1$)에는 정수 $p_i$ ($0 \leq p_i < i$)가 주어지며, 이는 가지 $i$가 가지 $p_i$의 윗부분 끝에 연결되어 있음을 뜻한다.

가지는 $0$부터 $n-1$까지 번호가 매겨져 있다. 가지 $0$은 나무의 뿌리에 연결되어 있으며, 이 가지에도 원숭이 한 마리가 들어갈 수 있다.

$n$개의 정수를 출력하라. $k$번째 정수는 정확히 $k$개의 가지로 이루어진 연결된 부분 트리의 개수를 $10^9+7$로 나눈 나머지이다.