트리의 변화

정점이 $n$개이고 간선이 $n-1$개인 연결 그래프를 트리라고 한다. 수찬이는 트리를 배양해서 관찰하는 일에 푹 빠져 있다. 여느 날처럼 트리를 지켜보던 그는 정점의 개수가 $2$의 거듭제곱, 즉 $2^0, 2^1, 2^2, \dots$인 트리는 다른 트리와 전혀 반응하지 않고 움직이지도 않는다는 사실을 우연히 발견했다. 수찬이는 이런 트리가 안정적인 상태에 있다고 정의했다.

정점이 6개인 트리는 안정적인 상태가 아니고, 정점이 4개인 트리는 안정적인 상태이다.

수찬이는 동료 과학자 지학이에게 이 사실을 알렸다. 연구 노트를 읽은 지학이는 "모든 트리는 안정적인 상태가 되는 쪽으로 변하지 않을까?"라고 말했다. 지학이의 말에 일리가 있다고 본 수찬이는 여러 실험으로 그 추측이 사실임을 확인했다. 그가 알아낸 성질은 이렇다. 안정적인 상태가 아닌 트리는 스스로 간선을 끊어 자신을 적절히 쪼개어 몇 개의 트리로 나누는데, 이때 각 트리의 정점 개수가 모두 $2$의 거듭제곱이 되게 해서 스스로를 안정적인 상태로 만든다. 수찬이가 이 성질을 알리자, 지학이는 실험 데이터를 분석하다가 간선을 끊는 데 에너지가 든다는 것을 알게 되었고, 트리가 안정적인 상태로 변하는 과정에서 끊기는 간선의 개수를 최소로 하는 방식으로 나뉜다는 성질을 추가로 밝혀냈다.

정점이 6개인 어떤 트리가 안정적인 상태로 변하는 한 예.

두 사람은 트리가 정확히 어떤 방법으로 나뉘는지 알아보려고, 지금까지 밝혀낸 두 성질을 지키면서 트리가 나뉘는 서로 다른 방법의 수를 세어 보기로 했다. 나뉘는 방법이 서로 다르다는 것은 끊긴 간선의 집합이 서로 다르다는 뜻이다. 간선이 끊기는 순서는 상관이 없다.

정점이 $n$개인 트리가 주어질 때, 이 트리가 두 성질을 지키면서 나뉘는 서로 다른 방법의 수를 구하는 프로그램을 작성하라.

첫째 줄에 트리의 정점 개수 $n$이 주어진다. ($2 \le n \le 4095$) 각 정점에는 $1$부터 $n$까지 번호가 하나씩 붙어 있다.

다음 $n-1$개 줄에는 트리의 간선 정보가 한 줄에 하나씩 주어진다. 각 줄에는 그 간선이 잇는 두 정점의 번호 $u$와 $v$가 공백을 사이에 두고 주어진다. ($1 \le u, v \le n$, $u \ne v$)

주어지는 그래프는 항상 트리이다.

첫째 줄에 두 성질을 지키면서 트리가 나뉘는 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 번째 예제의 트리를 그림으로 그리면 아래와 같다.

간선을 두 개 끊으면 정점이 $4 = 2^2$개인 트리, $2 = 2^1$개인 트리, $1 = 2^0$개인 트리로 나눌 수 있고, 방법은 아래 여섯 가지이다. 실선은 남아 있는 간선을, 점선은 끊긴 간선을 뜻한다.

두 번째 예제의 트리를 그림으로 그리면 아래와 같다.

이 트리는 간선을 세 개 끊어서 안정적인 상태가 된다. 나뉜 결과는 각 트리의 정점 개수에 따라 크게 두 가지로 분류된다.

• 정점이 $4 = 2^2$개인 트리 둘, $2 = 2^1$개인 트리 하나, $1 = 2^0$개인 트리 하나로 나뉘는 경우

  • 어느 방법에서나 6번 정점과 9번 정점을 잇는 간선, 6번 정점과 3번 정점을 잇는 간선은 반드시 끊긴다. 여기서 정점이 4개인 트리 하나와 정점이 2개인 트리 하나가 정해진다.
  • 3번 정점과 2, 5, 7, 11번 정점을 잇는 간선 가운데 하나를 골라 끊으면, 정점이 4개인 트리 하나와 정점이 1개인 트리 하나가 더 정해진다.
  • 따라서 이 방법으로 나눌 수 있는 경우의 수는 4이다.

정점의 개수가 4, 4, 2, 1인 트리 네 개로 나누는 방법의 예

• 정점이 $8 = 2^3$개인 트리 하나와 $1 = 2^0$개인 트리 셋으로 나뉘는 경우

  • 단말 정점(연결된 간선이 하나뿐인 정점) 세 개를 골라, 그 정점에 붙은 간선 세 개를 끊으면 된다.
  • 단말 정점이 8개이므로, 이 방법으로 나눌 수 있는 경우의 수는 $\binom{8}{3} = 56$이다.

정점의 개수가 8, 1, 1, 1인 트리 네 개로 나누는 방법의 예

따라서 방법의 수는 모두 60이다.