시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 111 9 9 14.516%

문제

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

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

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

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

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

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

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1

5
1 2
1 3
3 4
3 5
1 3 4 5 2

예제 출력 1

4

처음에 3번 정점에 고양이가 앉아서 탐색이 끝날 때까지 움직이지 않는다면 택희의 탐색 순서가 1 3 4 5 2가 되어 조건을 만족하게 된다.

따라서 예제의 경우 최소 필요한 고양이의 수는 1이며, 이때 가능한 시작점의 집합은 {1}, {3}, {4}, {5}가 되어 답이 4가 된다.

예를 들어 처음에 5번 정점에 고양이가 있었을 경우, 아래와 같은 방식으로 택희는 탐색을 마칠 수 있다.

 

0초 ~ 1초 : 고양이가 3번 정점으로 이동한다. 그 이후 택희는 인접한 방문하지 않은 정점 중 고양이가 있으며 번호가 가장 작은 3번 정점으로 이동한다. 수첩에는 3이 적힌다.

1초 ~ 2초 : 고양이는 1번 정점으로 이동한다. 택희는 인접한 방문하지 않은 정점 중 번호가 가장 작은 4번 정점으로 이동한다. 수첩에는 4가 적힌다.


2초 ~ 3초 : 고양이는 1번 정점에서 평화롭게 그루밍을 한다. 택희는 인접한 방문하지 않은 정점이 없으므로, 인접한 정점 중 수첩에 적힌 시점이 가장 오래 된 3번 정점으로 돌아간다.


3초 ~ 4초 : 고양이가 2번 정점으로 이동한다. 택희는 인접한 방문하지 않은 정점 중 번호가 가장 작은 5번 정점으로 이동한다. 수첩에는 5가 적힌다.


4초 ~ 5초 : 고양이는 가만히 앉아 있으며, 택희는 인접한 정점 중 수첩에 적힌 시점이 가장 오래 된 3번 정점으로 돌아간다.


5초 ~ 6초 : 고양이는 여전히 가만히 앉아 있으며, 택희는 1번 정점으로 올라간다.


6초 ~ 7초 : 가만히 있는 고양이를 따라 택희가 2번 정점에 도달한다. 수첩에 2가 적히며, 원하는 탐색 결과를 얻었다!