knight

Se dă un arbore cu $N$ noduri numerotate de la $1$ la $N$, înrădăcinat în nodul $1$. O mutare de cal dintr-un nod $u$ către un nod $v$ constă în parcurgerea unui traseu $u \to x \to y \to v$, unde $x$ este părintele lui $u$, $y$ este părintele lui $x$, iar $v$ este un fiu al lui $y$ astfel încât $v \neq x$ (vezi imaginea din dreapta). Observăm cum mutarea se aseamănă unei mutări de cal pe tabla de șah.

Cerință

Date fiind $N$ și părinții fiecărui nod $p_2, \ldots, p_N$ (nodul $1$, fiind rădăcina, nu are părinte), să se determine:

1. Numărul de noduri cu exact un fiu.

Date fiind, în plus, $Q$ perechi de noduri, să se determine pentru fiecare pereche dată $(a, b)$:

2. Dacă se poate ajunge din nodul $a$ în nodul $b$ făcând succesiv mutări de cal. În caz afirmativ, răspunsul va fi $1$, altfel $0$.
3. Numărul de trasee distincte ce pornesc din nodul $a$ și ajung în nodul $b$ făcând succesiv mutări de cal. Deoarece răspunsul poate fi destul de mare, se cere restul împărțirii acestuia la $10^9 + 7$.

Date de intrare

Prima linie va conține numărul cerinței $C \in \{1, 2, 3\}$. A doua linie va conține numărul de noduri din arbore $N$. A treia linie va conține $N - 1$ numere $p_2, p_3, \ldots, p_N$, reprezentând părintele fiecărui nod din arbore (nodul $1$, fiind rădăcina, nu are părinte). Oricare două numere consecutive de pe această linie sunt separate prin câte un spațiu.

Doar dacă $C \in \{2, 3\}$, a patra linie va conține numărul de perechi $Q$, următoarele $Q$ linii conținând numerele $a$ și $b$, separate printr-un spațiu, corespunzătoare fiecărei perechi $(a, b)$.

Date de ieșire

Dacă $C = 1$, se va afișa pe o singură linie numărul de noduri cu exact un fiu. În schimb, dacă $C \in \{2, 3\}$, se vor afișa $Q$ linii, fiecare conținând răspunsul la cerința $C$ corespunzător câte unei perechi $(a, b)$ din cele $Q$ date.

Restricții și precizări

• $C \in \{1, 2, 3\}$
• $1 \leq N \leq 200 \ 000$
• $1 \leq p_i < i$ pentru $2 \leq i \leq N$
• Dacă $C \in \{2, 3\}$, atunci:
  • $1 \leq Q \leq 200 \ 000$
  • $1 \leq a, b \leq N$ și $a \neq b$, pentru fiecare dintre cele $Q$ perechi date.
• Pentru $C = 3$, două trasee $s_1 \to s_2 \to \ldots \to s_k$ și $s'_1 \to s'_2 \to \ldots \to s'_\ell$ se consideră diferite dacă $k \neq \ell$ sau dacă există $1 \leq i \leq k$ astfel încât $s_i \neq s'_i$.

Exemplul 1

knight.in

1
7
1 1 3 3 3 4

knight.out

1

Explicație

Singurul nod din arbore care are exact un fiu este nodul $4$.

Exemplul 2

knight.in

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

knight.out

1
0
1

Explicație

Cele trei exemple vizează același arbore cu $N = 7$ noduri, schițat mai jos:

Sunt date $Q = 3$ perechi de noduri $(a, b)$:

1. $a = 7$, $b = 2$: Există două trasee ce pleacă din $7$ și ajung în $2$ prin mutări de cal:

   • $7 \to 4 \to 3 \to 5 \to 3 \to 1 \to 2$
   • $7 \to 4 \to 3 \to 6 \to 3 \to 1 \to 2$

   Așadar, pentru $C = 2$ răspunsul este $1$, iar pentru $C = 3$ este $2$.

2. $a = 7$, $b = 4$: Nu există niciun traseu ce pleacă din nodul $7$ și ajunge în nodul $4$ prin mutări succesive de cal, de unde răspunsul pentru ambele cerințe este $0$.

3. $a = 6$, $b = 2$: Există un singur traseu ce pleacă din $6$ și ajunge în $2$ prin mutări de cal, anume: $6 \to 3 \to 1 \to 2$. Prin urmare, răspunsul pentru ambele cerințe este $1$.

Exemplul 3

knight.in

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

knight.out

2
0
1

Explicație

Singura diferență față de exemplul anterior este numărul cerinței de rezolvat ($C = 3$ în loc de $C = 2$). Răspunsurile corespund numărului de trasee distincte: $2$, $0$, respectiv $1$.