42번 - 아귀도

아귀도의 호반우들은 $1$번부터 $N$번까지 $N$개의 정점으로 이루어지고 루트가 $1$번 정점인 트리로부터 깨달음을 얻고자 한다. 호반우들에게 $1$부터 $N$까지의 양의 정수로 이루어진 순열에서 일부가 $0$으로 바뀐 상태로 수열 $a_{1}, a_{2}, \cdots, a_{N}$이 주어진다. 해당 수열에서 $0$이 아닌 모든 $a_{i}$에 대해 $a_{i}$번 노드를 루트로하는 서브 트리에 포함된 모든 노드 번호가 $a_{i}$ 뒤에 나타나게 수열을 $1$부터 $N$까지의 양의 정수로 이루어진 순열로 완성시키는 경우의 수를 구해야 한다. 호반우를 도와 아귀도에서 깨달음을 얻어보자.

첫째 줄에 $N$이 주어진다. $(1 \leq N \leq 200\,000)$ 둘째 줄에 순열 $a_{1}, a_{2}, \cdots, a_{N}$이 공백을 두고 주어진다. $(0 \leq a_{i} \leq N)$ 셋째 줄부터 $N - 1$개의 줄에 걸쳐 트리의 각 간선이 잇는 두 정점의 번호 $u, v$가 공백을 두고 주어진다. $(1 \leq u, v \leq N)$

첫째 줄에 주어진 트리로 완성 가능한 본래의 순열의 개수를 $10^{9} + 7$로 나눈 나머지를 출력한다.