34046번 - 아귀도

문제

아귀도의 호반우들은 1ドル$번부터 $N$번까지 $N$개의 정점으로 이루어지고 루트가 1ドル$번 정점인 트리로부터 깨달음을 얻고자 한다.

호반우들은 1ドル$부터 $N$까지의 양의 정수로 이루어진 순열에서 일부가 0ドル$으로 바뀐 수열 $a_{1}, a_{2}, \cdots, a_{N}$이 주어질 때, 다음 조건을 모두 만족하는 $b_{1}, b_{2}, \cdots, b_{N}$의 개수를 구해야 한다.

• $b_{1}, b_{2}, \cdots, b_{N}$은 순열이다. 즉, 1ドル$부터 $N$까지의 양의 정수가 한 번씩 나타나야 한다.
• $a_{i} > 0$인 모든 $i$에 대하여, $b_{i} = a_{i}$이다.
• $a_{i} > 0$인 모든 $i$와 $a_{j} = 0$인 모든 $j$에 대하여 $b_{j}$번 노드가 $b_{i}$번 노드의 자손이라면 $j > i$를 만족한다.

호반우를 도와 아귀도에서 깨달음을 얻어보자.

입력

첫째 줄에 $N$이 주어진다. $(1 \leq N \leq 200,000円)$

둘째 줄에 수열 $a_{1}, a_{2}, \cdots, a_{N}$이 공백을 두고 주어진다. $(0 \leq a_{i} \leq N ; a_{i} = a_{j} \Rightarrow i = j$ 또는 $a_{i} = 0)$

셋째 줄부터 $N - 1$개의 줄에 걸쳐 트리의 각 간선이 잇는 두 정점의 번호 $u, v$가 공백을 두고 주어진다. $(1 \leq u, v \leq N)$

출력

첫째 줄에 주어진 트리로 완성 가능한 $b_{1}, b_{2}, \cdots, b_{N}$의 개수를 10ドル^{9} + 7$로 나눈 나머지를 출력한다.

제한

힌트