Gepetto

Grandfather Gepetto's family is very large, consisting of himself and $N-1$ of his descendants (children, grandchildren, great-grandchildren, great-great-great-grandchildren, etc.).

Since Gepetto cannot remember the names of all the members of his family, he has assigned each of them (including himself) a unique number between $1$ and $N$.

Moreover, since Gepetto doesn't get along well with his relatives by marriage, he only remembers, for each person, who their parent is, that parent also being a descendant of Gepetto. For each $1 \le i \le n$, let $P_i$ be the number associated with the parent of person $i$. We consider the number associated with Gepetto's parent to be $0$.

On Children's Day, Gepetto wants to give each member of his family (including himself) a gift, but he is torn over the order in which to give out the gifts. An order of giving out the gifts can be represented as a permutation $A_1, A_2, \ldots, A_n$, meaning that:

• Gepetto will give the first gift to the person numbered $A_1$;
• Gepetto will give the second gift to the person numbered $A_2$;
• $\ldots$
• Gepetto will give the last gift to the person numbered $A_n$.

Gepetto considers a gift-giving order to be good if every person in the family receives their gift earlier than all of their children.

After choosing a good gift-giving order $V_1, V_2, \ldots V_n$, Gepetto nevertheless wonders what position this order would occupy in the lexicographically sorted$^1$ sequence of all good gift-giving orders.

Since this position can be very large, Gepetto is satisfied with just its remainder modulo $10^9+7$.

$^1$ An order $A_1,A_2,\ldots,A_N$ is lexicographically smaller than another order $B_1,B_2,\ldots,B_N$ if there exists a position $i$ ($1 \le i \le N$) such that:

• $A_j=B_j$, for all indices $j$ satisfying $1 \le j<i$;
• $A_i < B_i$.

Implementation Details

You must implement the function

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

which receives as parameters:

• $N$, the number of family members.
• $P$, a vector indexed from $0$ where $P_i$ represents the parent of person $i + 1$, for every $0 \leq i < N$.
• $V$, a permutation of the numbers $\{1, 2, \ldots N\}$, representing the gift-giving order chosen by Gepetto.

The function must return a single integer, representing the index of the permutation in the lexicographically sorted sequence, modulo $1 \ 000 \ 000 \ 007$.

Constraints and Notes

• $1 \leq N\leq 1 \ 000 \ 000$
• $0 \leq P_i \leq N$
• $1 \leq V_i \leq N$
• It is guaranteed that there exists exactly one $i$ for which $P_i=0$. This $i$ is the number associated with Gepetto.
• It is guaranteed that the graph formed by all the edges $(i, P_i)$ is a tree (an acyclic undirected graph).
• It is guaranteed that each number from $1$ to $N$ appears exactly once in the sequence $V$. In other words, it is guaranteed that the sequence $V$ is a permutation of order $N$.

Example 1

input

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

output

67

Explanation

The family tree from the first example:

Example 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

Explanation

The family tree from the second example: