청소 로봇

새로 지어진 ICPC 타운에는 N개의 교차점이 있고, 이들은 N − 1개의 도로로 연결되어 있다. 어떤 교차점에서 출발해도 도로를 하나 이상 지나면 다른 모든 교차점에 도달할 수 있다. 모든 교차점을 잘 관리하기 위해 정부 환경청은 최신형 청소 로봇을 배치하려 한다. 각 로봇은 청소 능력 외에도 도로로 연결된 교차점 사이를 이동하는 능력을 갖추고 있다. 그러나 짐작할 수 있듯이 이런 로봇은 값이 싸지 않다. 그래서 환경청은 다음과 같은 배치 계획을 고려하고 있다.

$T_k$를 k번째 로봇이 청소해야 하는 교차점의 집합(로봇의 작업)이라 하고, $|T_k| \ge 1$을 $T_k$에 속한 교차점의 수라 하자. $T_k$의 교차점들은 하나의 경로를 이룬다. 즉, $v_i \in T_k$이고 $i \neq j$이면 $v_i \neq v_j$인 수열 $v_1, v_2, \ldots, v_{|T_k|}$이 존재해서 이 수열에서 인접한 두 교차점이 도로로 연결되어 있다. 모든 로봇의 $T$의 합집합은 ICPC 타운의 모든 교차점의 집합과 같다. 한편, 두 로봇이 같은 교차점을 공유하지는 않는다. 즉, $i \neq j$이면 $T_i \cap T_j = \emptyset$이다.

비효율적인 운영에 대한 시민의 불만을 피하기 위해 배치 계획은 기약이어야 한다. 다시 말해, $T_i \cup T_j$가 더 긴 경로를 이루는 두 로봇 i, j가 있어서는 안 된다. 환경청은 모든 작업이 기약이기만 하면 사용하는 로봇의 수가 최소인지는 신경 쓰지 않는다. 이 문제에서 여러분의 임무는 타운의 구조가 주어졌을 때 가능한 배치 계획의 수를 세는 것이다. 계획은 위의 모든 조건을 만족할 때에만 가능하다.

예를 들어 N = 6이고 도로가 {(1, 3),(2, 3),(3, 4),(4, 5),(4, 6)}이라 하자. 다음 그림과 같이 가능한 배치 계획은 5가지이다.

• 첫 번째 계획은 2대의 로봇(그림에서 A, B)으로 {1, 2, 3}과 {4, 5, 6}을 청소한다.
• 두 번째 계획은 3대의 로봇(그림에서 A, B, C)으로 {1, 3, 4, 6}, {2}, {5}를 청소한다.
• 세 번째 계획은 3대의 로봇으로 {1, 3, 4, 5}, {2}, {6}을 청소한다.
• 네 번째 계획은 3대의 로봇으로 {1}, {2, 3, 4, 6}, {5}를 청소한다.
• 다섯 번째 계획은 3대의 로봇으로 {1}, {2, 3, 4, 5}, {6}을 청소한다.

이 경우에 다른 계획은 가능하지 않다. 예를 들어 계획 {{1, 3}, {2}, {4, 5, 6}}은 작업 {1, 3}과 {2}를 더 긴 경로 {1, 3, 2}로 합칠 수 있으므로 가능하지 않다. 계획 {{1, 2, 3, 4}, {5}, {6}}도 {1, 2, 3, 4}가 경로가 아니므로 가능하지 않다.

입력의 첫 줄에는 교차점의 수를 나타내는 정수 N (1 ≤ N ≤ 100 000)이 주어진다. 다음 N − 1개 줄에는 각각 교차점 $u_i$와 교차점 $v_i$를 연결하는 도로를 나타내는 두 정수 $u_i$ $v_i$ (1 ≤ $u_i$ < $v_i$ ≤ N)가 주어진다. 어떤 교차점에서 출발해도 도로를 하나 이상 지나면 다른 모든 교차점에 도달할 수 있음이 보장된다.

가능한 배치 계획의 수를 한 줄에 정수로 출력한다. 이 값은 클 수 있으므로 1 000 000 007로 나눈 나머지를 출력한다.