고양이 우선 탐색

택희는 어느 날 눈을 떠 보니 어떤 트리의 1번 정점에 놓여 있었다. 이 트리에는 택희 외에도 고양이가 몇 마리 있을 수 있다.

이 트리에서는 매초 아래 두 가지 일이 순서대로 한 번씩 일어난다.

• 모든 고양이가 가만히 있거나, 인접한 다른 정점으로 한 번 이동한다. 각 고양이는 독립적으로 움직인다.
• 택희가 인접한 정점 중 하나로 한 번 이동한다. 택희는 가만히 있을 수 없다.

택희는 그래프의 특성을 파악한 뒤 다음과 같은 탐색 전략을 세웠다. 처음에 택희는 1이 적힌 수첩과 펜을 들고 1번 정점 위에 서 있다.

1. 현재 정점에 인접한 다른 정점들 중 아직 수첩에 기록되지 않은 정점들의 집합을 V라고 하자.
   • V가 비어 있다면, 현재 정점에 인접한 정점 중 수첩에 적힌 지 가장 오래된 정점으로 되돌아간다.
   • V 안에 고양이가 있는 정점이 있다면, 그러한 정점들 중 번호가 가장 작은 정점으로 간다.
   • 그러한 정점이 없다면, V 안에서 번호가 가장 작은 정점으로 간다.
2. 도착한 정점의 번호가 수첩에 적혀 있지 않다면 그 번호를 수첩에 기록한다.
3. 수첩에 N개의 정수가 적힐 때까지 (1)과 (2)를 반복한다. (1)과 (2)를 한 번 반복하는 데 1초가 걸린다.

탐색 과정에서 고양이들, 또는 고양이들과 택희가 같은 정점 위에 있게 될 수도 있다.

택희는 무사히 탐색을 마친 뒤 수첩에 적힌 N개의 정수를 바라보았다. 그 순간 알람이 울렸고, 택희는 꿈에서 깨어났다.

택희는 꿈에서 본 N개의 정수를 기억하고 있으며, 트리의 구조도 정확히 기억하고 있다.

택희는 이러한 탐색을 가능하게 하는 최소 고양이 수와, 각 고양이의 시작점이 어디였는지 궁금해졌다. 택희를 위해, 고양이가 최소 수만큼만 트리 위에 있었을 때 가능한 시작점 집합의 개수를 세어 주자.

시작점 집합이란, 고양이 수만큼의 길이를 갖는 배열로, 각 고양이가 서 있는 정점 번호를 비내림차순으로 나열한 것이다. 이 배열에서 서로 다른 원소가 하나 이상 있으면 서로 다른 집합으로 센다.

첫째 줄에 트리의 정점 수 N이 주어진다. ($2 \le N \le 10^5$)

둘째 줄부터 N-1개의 줄에 걸쳐 간선의 정보 U V가 주어진다. 이는 두 정점 U와 V를 잇는 간선이 트리 위에 있다는 뜻이다. ($1 \le U, V \le N$, $U \ne V$)

주어지는 트리는 올바르게 연결된 트리임이 보장된다.

마지막 줄에는 공백으로 구분된 N개의 정수가 주어진다. 택희가 수첩에 적은 정수가 순서대로 주어진다. 수열의 첫 값은 항상 1이다. 이 수열에는 1부터 N까지의 정수가 정확히 한 번씩 등장하며, 고양이들이 최선을 다해 도울 경우 이 수열이 탐색 순서로 가능함이 보장된다.

고양이가 최소 수만큼만 있었을 때, 가능한 서로 다른 고양이 시작점 집합의 수를 $10^9+7$로 나눈 나머지를 출력한다.