Problem Brief

Build Monuments

In the nation of Coderland, the layout of the cities can be depicted as a tree structure with totalCities numbered from 1 to totalCities. These cities are interconnected by totalCities - 1 two-way routes, where the i-th route links cityStart[i] with cityEnd[i].

The ruler of Coderland intends to install one of monumentTypes unique monuments in each city. However, the following condition must be satisfied:

No two directly connected cities or two cities that share a common neighboring city can have identical monument types.

Your task is to calculate the total number of valid configurations for placing monuments in every city based on these rules. Since the resulting number could be extremely large, return the answer modulo (10^9 + 7).

Two cities are regarded as adjacent if there is a direct connection between them via a route.

Parameters:

int monumentTypes: The number of distinct monument styles available.

int totalCities: The total number of cities in the kingdom.

int[] routeStart: An array representing the starting city of each road.

int[] routeEnd: An array representing the ending city of each road.

Returns:

int: The number of valid ways to construct the monuments, computed modulo (10^9 + 7).

1Example 1

Input

monumentTypes = 4, totalCities = 3, routeStart = [1, 1], routeEnd = [2, 3]

Output

Explanation

City 1 must not share the same monument style as City 2 or City 3 since they are directly connected through roads. Similarly, City 2 and City 3 cannot have identical monument styles because both are linked to City 1. As a result, each city requires a unique monument type. There are m = 4 available monument styles. Any combination of 3 different styles assigned to the cities in any sequence will be valid. For instance, possible combinations include [1, 2, 3], [2, 1, 3], and [4, 1, 3]. In total, there are 24 unique valid arrangements. Therefore, the answer is 24 modulo (10^9 + 7), which equals 24.