시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB178321710.968%

문제

설곽국은 1부터 N까지의 번호가 매겨진 N개의 도시로 이루어진 국가이다. 도시 사이에는 두 도시를 연결하는 N-1개의 도로가 존재하며 모든 도시들은 연결되어 있다. 모든 도로의 길이는 1으로 같다.

최근 설곽국에서는 옆나라 경곽국으로부터 들어온 신종 바이러스가 유행하고 있다. 설곽국의 보건복지부 장관 근영이는 바이러스를 확산시키는 가장 큰 요인은 장거리 여행이라고 생각하여, 몇몇 도시를 봉쇄하고 봉쇄된 도시와 연결된 도로를 폐쇄하려고 한다.

근영이가 생각하기에 장거리 여행이란 이동거리가 K 이상이고 같은 도시를 두 번 이상 지나지 않는 여행을 의미한다.

예를 들어, K = 3이고 도시와 도로의 모양이 아래 그림과 같다고 하자.

이 때 장거리 여행으로 가능한 경로는 1,2,3,6번 도시를 순서대로 지나는 경로나, 5,3,6,7번 도시를 순서대로 지나는 경로 등이 있다. 물론 이 외에도 여러가지 장거리 여행의 방법이 있다.

만약 여기서 3번 도시를 봉쇄한다면, 같은 도시를 두 번 이상 지나지 않는 어떤 경로도 길이가 2를 넘지 않으므로 장거리 여행은 불가능해진다. 또한 모든 도시를 봉쇄했을 때도 장거리 여행은 불가능해진다.

근영이는 적절한 도시들을 봉쇄하여 장거리 여행이 불가능하게 만들고 싶다. 장거리 여행이 불가능하도록 도시를 봉쇄하는 방법의 수를 구하여라.

입력

첫째 줄에 도시의 개수를 나타내는 자연수 N과 근영이가 생각하고 있는 양의 정수 K가 주어진다. (1 ≤ K ≤ N ≤ 300,000)

둘째 줄부터 N번째 줄까지는 도로의 정보를 나타내는 두 자연수 x, y (1 ≤ x, y ≤ N)가 주어진다. 이는 x번 도시와 y번 도시를 연결하는 도로가 존재함을 의미힌다.

출력

첫째 줄에 장거리 여행이 불가능하도록 도시를 봉쇄하는 방법의 수를 109+7로 나눈 나머지를 출력한다.

예제 입력 1

4 1
1 2
2 3
3 4

예제 출력 1

8

봉쇄할 도시의 집합으로 가능한 경우는 {1, 3}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}의 8가지가 있다.

예제 입력 2

5 3
1 2
1 3
1 4
1 5

예제 출력 2

32

예제 입력 3

7 3
1 2
2 3
2 4
3 6
3 5
6 7

예제 출력 3

104

출처

High School > 서울과학고등학교 > 2020 SciOI #1 F번