17077번 - 고양이 우선 탐색

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

이 트리에서는 매초마다 아래와 같은 일이 순서대로 한 번씩 일어난다.

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

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

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

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

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

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

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

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

첫째 줄에 트리의 정점의 수 N이 주어진다. (2 ≤ N ≤ 10⁵)

둘째 줄부터 N-1개의 줄에 걸쳐, 간선의 정보 U V가 주어진다. 이는 두 정점 U와 V를 잇는 간선이 트리 위에 존재했다는 의미이다. (1 ≤ U, V ≤ N, U ≠ V)

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

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

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