Gepetto

Familia bunicului Gepetto este foarte numeroasă, fiind formată din el însuși și din $N-1$ descendenți ai acestuia (copii, nepoți, stră-nepoți, stră-stră-stră-nepoți, etc.).

Deoarece Gepetto nu poate reține numele tuturor membrilor familiei sale, el a atribuit fiecăruia dintre aceștia (inclusiv lui însuși) câte un număr unic între $1$ și $N$.

În plus, deoarece Gepetto nu se înțelege bine cu rudele sale prin alianță, el ține minte pentru fiecare persoană doar cine este părintele său care este la rândul său un descendent al lui Gepetto. Pentru fiecare $1 \le i \le n$, fie $P_i$ numărul asociat părintelui persoanei $i$. Considerăm că numărul asociat părintelui lui Gepetto este $0$.

De ziua copilului, Gepetto vrea să le ofere tuturor membrilor familiei sale (inclusiv lui însuși) câte un cadou, însă este frământat de ordinea în care să ofere cadourile. O ordine de oferire a cadourilor poate fi reprezentată ca o permutare $A_1, A_2, \ldots, A_n$, cu semnificația că:

• Gepetto va oferi primul cadou persoanei cu numărul $A_1$;
• Gepetto va oferi al doilea cadou persoanei cu numărul $A_2$;
• $\ldots$
• Gepetto va oferi ultimul cadou persoanei cu numărul $A_n$.

Gepetto consideră că o ordine de oferire a cadourilor este bună dacă fiecare persoană din familie își va primi cadoul mai devreme decât toți copiii săi.

După ce a ales o ordine bună de oferire a cadourilor $V_1, V_2, \ldots V_n$, Gepetto se întreabă totuși pe ce poziție s-ar afla această ordine în șirul sortat lexicografic$^1$ al tuturor ordinilor bune de oferire a cadourilor.

Deoarece această poziție poate fi foarte mare, Gepetto este mulțumit și cu restul acesteia modulo $10^9+7$.

$^1$ O ordine $A_1,A_2,\ldots,A_N$ este mai mică lexicografic decât o altă ordine $B_1,B_2,\ldots,B_N$ dacă există o poziție $i$ ($1 \le i \le N$) pentru care:

• $A_j=B_j$, pentru toți indicii $j$ care satisfac $1 \le j<i$;
• $A_i < B_i$.

Detalii de implementare

Va trebui să implementezi funcția

int solve(int N, std::vector<int> P, std::vector<int> V)

care primește ca parametri:

• $N$, numărul de membri ai familiei.
• $P$, vector indexat de la $0$ unde $P_i$ reprezintă părintele persoanei $i + 1$ pentru oricare $0 \leq i < N$.
• $V$, o permutare a numerelor $\{1, 2, \ldots N\}$, reprezentând ordinea de dăruire a cadourilor aleasă de Gepetto.

Funcția va returna un singur număr întreg, reprezentând indicele permutării în șirul sortat lexicografic modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq N\leq 1 \ 000 \ 000$
• $0 \leq P_i \leq N$
• $1 \leq V_i \leq N$
• Se garantează că există exact un $i$ pentru care $P_i=0$. Acest $i$ este numărul asociat lui Gepetto.
• Se garantează că graful format din toate muchiile $(i, P_i)$ este un arbore (un graf neorientat aciclic).
• Se garantează că fiecare număr de la $1$ la $N$ apare o singură dată în șirul $V$. În alte cuvinte, se garantează că șirul $V$ este o permutare de ordin $N$.

Exemplul 1

input

6
3 3 0 3 3 3
3 4 6 1 2 5

output

67

Explicație

Arborele genealogic din primul exemplu:

Exemplul 2

input

10
4 9 9 0 1 4 9 4 4 8
4 6 1 8 5 10 9 3 7 2

output

5158

Explicație

Arborele genealogic din al doilea exemplu: