왕의 색깔

아주 먼 곳에 신비로운 나무 왕국(정식 명칭으로는 "연결 무방향 단순 비순환 그래프 연합 왕국")이 있다. 이 왕국은 유엔에서 주권 국가로 인정받지 못해 왕이 몹시 슬퍼하고 있다. 유엔 회원국이 되려면 유엔 웹사이트에 걸 수 있는 국기를 만들어야 한다.

국기에는 물론 왕이 가장 좋아하는 나무가 들어가며, 이 나무에는 n개의 노드가 있다. 왕은 나무를 흑백으로만 칠해도 만족했겠지만 왕비를 위해서라도 나무에 자녀 k명이 각각 가장 좋아하는 색을 모두 넣기로 했다(자녀들은 모두 서로 다른 색을 좋아한다). 인접한 두 노드는 같은 색으로 칠할 수 없고, 그 외에는 정확히 이 k개의 색으로 나무를 칠하는 모든 색칠이 국기 후보가 될 수 있다.

가능한 국기는 모두 몇 가지인가?

첫째 줄에 두 정수 n과 k가 주어진다(2 ≤ k ≤ n ≤ 2 500). n은 왕이 가장 좋아하는 나무의 노드 수이고 k는 자녀 수이다. 이어서 나무의 간선을 나타내는 n − 1개의 줄이 주어진다. 이 중 i번째 줄에는 i보다 작은 음이 아닌 정수 pi가 주어지며, 노드 pi가 노드 i의 부모임을 뜻한다.

노드는 0부터 n − 1까지 번호가 매겨져 있고 나무의 루트는 노드 0이다. 나무가 국기 위에 놓이는 방식은 이미 정해져 있으며, 남은 것은 색을 지정하는 일뿐이다.

가능한 서로 다른 색 지정의 수를 출력한다. 그 수가 매우 클 수 있으므로 왕은 답을 1 000 000 007로 나눈 나머지로 알려 달라고 요청했다.