Nhãn Không Tăng Trên Cây · canuc80k7110

Cho một cây có gốc tại đỉnh $1$ . Với mỗi đỉnh $v > 1$ , cha trực tiếp của $v$ là $p_{v}$ ; luôn có $1 \leq p_{v} < v$ .

Hãy gán cho mỗi đỉnh một số nguyên thuộc $[1, D]$ sao cho nhãn của một đỉnh không lớn hơn nhãn của cha nó. Đếm số cách gán nhãn, lấy dư theo $1000000007$ .

Input

Dòng đầu chứa hai số nguyên $N, D$ .
Nếu $N > 1$ , dòng tiếp theo chứa $N - 1$ số nguyên $p_{2}, p_{3}, \dots, p_{N}$ .

Output

In số cách gán nhãn hợp lệ modulo $1000000007$ .

Constraints

$1 \leq N \leq 3000$ .
$1 \leq D \leq 1 0^{9}$ .
$1 \leq p_{v} < v$ với mọi $2 \leq v \leq N$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 9$ và $D \leq 6$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

1 4

Output

Giải thích: Cây chỉ có đỉnh gốc, nên có thể chọn một trong bốn nhãn.

Test 2

Input

3 2
1 1

Output

Giải thích: Nếu gốc mang nhãn $1$ thì hai con đều phải mang nhãn $1$ ; nếu gốc mang nhãn $2$ thì mỗi con có hai lựa chọn, tổng cộng $1 + 2 \cdot 2 = 5$ cách.

Ý tưởng: Với mỗi đỉnh u, đặt F_u(x) là số cách gán nhãn trong cây con của u khi nhãn của u không vượt quá x. Nếu nhãn của u bằng đúng s, mỗi cây con gốc v có F_v(s) cách và các cây con độc lập. Do đó
Ý tưởng: [ F_u(x)=\sum_{s=1}^{x}\prod_{v\text{ là con của }u}F_v(s). ]
Ý tưởng: Quy nạp theo cây cho thấy F_u là đa thức có bậc bằng số đỉnh trong cây con của u. Vì vậy chỉ cần tính F_1(0),...,F_1(N) rồi nội suy tại D.
Ý tưởng: Ta duyệt x=1..N; tại mỗi x, xử lý đỉnh theo thứ tự giảm dần. Vì p_v<v, mọi con của u đã được tính tại cùng x.
Ý tưởng: Độ phức tạp là O(N^2) thời gian và O(N^2) bộ nhớ.