The organizational structure of a Salesforce instance can be visualized as a tree of g_nodes departments, numbered from 1 to g_nodes.

These departments are interconnected by g_nodes - 1 bidirectional communication channels, where the ith channel links department g_from[i] to department g_to[i].

The CTO wants to deploy one of m different types of custom Salesforce apps in each department such that no two departments that are directly connected or share a common neighboring department utilize the same app type.

Determine the number of valid ways to assign the apps across all departments as described. Since the result may be large, return it modulo 10^9 + 7.

Two departments are considered connected if they share a direct communication channel.

Example m = 4 g_nodes = 3 g_from = [1, 1] g_to = [2, 3]

Department 1 cannot use the same app type as departments 2 or 3 because they are directly connected.

Departments 2 and 3 must also have different app types because they both connect to department 1.

There are 4 app types available. Any 3 distinct types can be assigned in any order.

Examples of valid assignments include:

[1, 2, 3] [2, 1, 3] [4, 1, 3] ...

There are

4 × 3 × 2 = 24

valid assignments.

Function Description

Complete the function:

int getDeploymentWays(
    int m,
    int g_nodes,
    vector<int> g_from,
    vector<int> g_to
)

Parameters int m: the number of app types available. int g_nodes: the number of departments. int g_from[g_nodes-1]: one endpoint of each communication channel. int g_to[g_nodes-1]: the other endpoint of each communication channel. Returns int: the number of valid ways to assign apps, modulo 10^9 + 7.

Input Format For Custom Testing The first line contains an integer m.

The second line contains an integer g_nodes.

The third line contains an integer g_edges (= g_nodes - 1).

The next g_edges lines each contain an integer g_from[i].

The next g_edges lines each contain an integer g_to[i].

Sample Case 0 Input 3 4 3 1 1 2 2 3 4

which corresponds to

m = 3 g_nodes = 4 g_from = [1, 1, 2] g_to = [2, 3, 4] Output 6

Explanation

The communication tree is:

2

/
1 4
3 Pairs (1,2), (1,3), and (2,4) are directly connected. Pair (1,4) shares department 2 as a common neighbor. Pair (2,3) shares department 1 as a common neighbor. Pair (3,4) may use the same app type.

Thus, three distinct app types are required.

The valid assignments are:

[1,2,3,3] [2,1,3,1] [3,1,2,1] [1,3,2,2] [2,3,1,2] [3,2,1,1]

Hence, the answer is:

6