카지노와 여행

John은 막 새 차를 샀고 전국을 여행할 계획을 세우고 있다. 이 나라에는 N개의 도시가 있으며, 그중 일부는 양방향 도로로 연결되어 있다. 도로는 N - 1개이며, 모든 도시에서 다른 모든 도시로 갈 수 있다. 도시에는 1부터 N까지의 번호가 붙어 있다.

John은 먼저 여정을 시작할 도시를 선택해야 한다. 그 후 한 도시에서 하루를 보낸 다음, 현재 도시와 직접 연결되어 있고 아직 방문하지 않은 도시 중 하나를 무작위로 선택해 이동한다. 그는 이 규칙을 지키면서 더 이상 이동할 수 없을 때까지 이를 반복한다.

시작 도시를 선택하기 위해 John은 친구 Jack에게 조언을 구한다. Jack 역시 대규모 카지노 사업을 시작하려 하며, 일부 도시에 카지노를 열고 싶어 한다(도시당 최대 1개이며, 어디에도 열지 않을 수도 있다). Jack은 John을 잘 알기에 John이 카지노가 있는 도시를 방문하면 여정을 계속하기 전에 정확히 한 번 도박한다는 것을 안다.

또한 John이 기분이 좋은 상태로 카지노에 들어가면 기분이 나쁜 상태로 나오고, 그 반대도 마찬가지라는 것을 안다. Jack은 John의 친구이므로 John이 여정을 마치는 순간 기분이 좋기를 바란다. John은 여정을 시작하기 전에는 기분이 좋다.

John이 어떻게 이동하더라도 마지막에 기분이 좋도록 Jack이 John의 시작 도시와 카지노를 지을 도시들을 선택하는 방법은 몇 가지인가? 답을 109 + 7로 나눈 나머지를 출력한다.

첫째 줄에 도시의 수를 나타내는 양의 정수 N (1 ≤ N ≤ 100000)이 주어진다.

다음 N - 1개의 줄에는 두 수 a, b (1 ≤ a, b ≤ N)가 하나의 공백으로 구분되어 주어지며, 이는 도시 a와 b가 양방향 도로로 연결되어 있다는 뜻이다.

문제의 답을 109 + 7로 나눈 나머지인 수 하나를 출력한다.

예제 1: If Jack이 John의 시작 도시로 도시 1을 선택하면, 카지노를 0개 지어 John이 계속 행복하게 하거나 두 도시에 모두 카지노를 지을 수 있다. 후자의 경우 John은 도시 1의 카지노를 방문해 불행해진 다음 도시 2로 가서 그곳의 카지노를 방문하고 행복해지며, 도시 1로 돌아갈 수 없으므로 그곳에서 여정이 끝난다. If Jack이 시작 도시로 도시 2를 선택하는 경우에는 모든 것이 대칭이므로 답은 4이다.

예제 2: If Jack이 John에게 도시 1에서 시작하라고 하면 카지노를 0개 또는 2개의 도시에 지을 수 있다(총 4가지 가능성). 도시 2에서 시작하라고 하면 John의 여정에는 도시 2와 1 또는 도시 2와 3이 포함된다. 따라서 Jack은 카지노를 하나도 짓지 않거나 세 도시에 모두 지어야 한다. 다른 선택을 하면 John이 불행한 상태로 여정을 마칠 위험이 있다. 도시 3에서 시작하는 경우는 도시 1에서 시작하는 경우와 대칭이므로, 모두 합해 4 + 2 + 4 = 10가지 선택지가 있다.