Alice's country hasnnncities andn1n-1n1undirected roads. Each road connects two different cities. And One city can go to any other city using thesen1n-1n1roads, which means that these cities form a tree. The distance between two cities is defined as the number of roads on their shortest path. The country is fighting against the Covid-19. To facilitate the management of the country, thesennncities will be divided into some areas. Each city must be exactly in one area. Once a Covid-19 occurs in an area, this area will be closed immediately. Each area must contain at least one city, must be a connected component, and its diameter must not be greater thankkk. The diameter of an area is defined as the maximum distance between two cities belonging to this area. Alice wants to know how many different ways to divide the cities into some areas. two ways are different if and only if there exists any city such that the area containing this city in these two ways are different. As the answer may be too large, print it modulo109+710^9+7109+7.
Alice's country has nnn cities and n−1n-1n−1 undirected roads. Each road connects two different cities. And One city can go to any other city using these n−1n-1n−1 roads, which means that these cities form a tree. The distance between two cities is defined as the number of roads on their shortest path. The country is fighting against the Covid-19. To facilitate the management of the country, these nnn cities will be divided into some areas. Each city must be exactly in one area. Once a Covid-19 occurs in an area, this area will be closed immediately. Each area must contain at least one city, must be a connected component, and its diameter must not be greater than kkk. The diameter of an area is defined as the maximum distance between two cities belonging to this area. Alice wants to know how many different ways to divide the cities into some areas. two ways are different if and only if there exists any city such that the area containing this city in these two ways are different. As the answer may be too large, print it modulo 109+710^9+7109+7.
