Secret

Într-o companie, sunt $N$ angajați. Angajatul $1$ este șeful companiei, iar fiecare dintre ceilalți angajați are un șef. Șeful celui de-al $i$-lea angajat este $S_i \ (1 \leq S_i < i)$. Angajații doresc să transmită mai multe secrete între ei, dar fiecare angajat poate comunica direct doar cu șeful său și cu persoanele care se află sub șefia angajatului ales. Mai exact, persoana $i$ poate vorbi cu persoana $j$ dacă și numai dacă $S_j = i$ sau $S_i = j$.

O submulțime $Q \subseteq \{1, 2, \dots, N\}$ de angajați, vor să transmită secrete între ei. Inițial, fiecare persoană din $Q$ are secretul său. Dacă o persoană știe un secret, îl poate transmite la oricare dintre persoanele cu care poate comunica direct. Din păcate, aflarea vreunuia dintre secrete de prea mulți angajați ar putea duce la falimentul companiei, așadar, vrei să fie cât mai puține persoane care îl află. Notăm cu $f(Q)$ numărul minim de persoane care trebuie să afle cel puțin un secret astfel încât fiecare angajat din $Q$ să știe secretul fiecărui alt angajat din $Q$.

În figura din dreapta, persoana $1$ poate comunica direct cu persoanele $2, 3, 4$. Persoana $2$ poate comunica direct cu persoanele $1, 5$. Persoana $6$ poate comunica direct cu persoanele $3, 7$.

Pe același exemplu avem $f(\{3, 4, 5, 9\}) = 6$, deoarece pentru a transmite secretul e necesar și suficient să fie comunicat persoanelor $1, 2, 3, 4, 5, 9$.

Cerință

Se vor rezolva $T$ scenarii. Pentru fiecare scenariu, trebuie să rezolvați următoarea problemă:

Se dă $N, K$ și șeful $S_i$ al fiecărui angajat $i$ de la $2$ la $N$. Află numărul de submulțimi $Q \subseteq \{1, 2, \dots, N\}$ pentru care $f(Q) = K$. Afișați acest număr modulo $10^9 + 7$.

Date de intrare

Pe prima linie a intrării se află numărul $T$ de scenarii.
Pentru fiecare $i$ de la $1$ la $T$ se vor afla câte două linii, reprzentând datele celui de al $i$-lea scenariu.
Pe linia $2 \cdot i$ a intrarii de afla doua numere $N$ si $K$.
Pe linia $2 \cdot i + 1$ se află un șir $S$ de lungime $N - 1$. Al $i$-lea element reprezentând șeful celui de al $i+1$-lea angajat.

Date de ieșire

Se va afișa un singur număr, reprezentând numărul de submulțimi care satisfac proprietatea din cerință (modulo $10^9 + 7$).

Restricții și precizări

• $1 \leq K \leq N \leq 3 \ 000$;
• Notăm cu $s_N$ suma valorilor lui $N$ din toate scenariile
• $1 \leq s_N \leq 6 \ 000$

Exemplul

stdin

3
4 3
1 2 3
6 4
1 1 2 2 1
7 5
1 2 2 2 3 3

stdout

4
20
38

Explicație

În primul scenariu, mulțimile de cost $3$ sunt $\{ \{1, 3 \}; \{1, 2, 3 \}; \{2, 4 \}; \{2, 3, 4 \} \}$. De asemenea, primul scenariu se încadreaza în primul subtask.