### PROBLEM LINK:

**Author:** Bipin Baburaj

**Tester:** Sergey Kulik

**Editorialist:** Mugurel Ionut Andreica

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

### PROBLEM:

A rooted tree with **N** nodes is considered. We need to assign a color from **1** to **K** to each node of the tree in such a way that every pair of nodes **(A,B)**, where **A** is the parent of **B**, has different colors.

### QUICK EXPLANATION:

The answer is K*(K-1)^{N-1}. Note that the actual tree is not given. This is because there is the same answer for every tree with **N** nodes (and for the given **K**).

### EXPLANATION:

We can choose any of the **K** colors for the root of the tree. Then we can choose any color except the root’s color for any of the root’s children. Then, for every child of a child of the root we can choose any color except that of its parent, and so on. Thus, for each of the other **N-1** nodes we have **K-1** choices for its color. The overall answer is K*(K-1)^{N-1}.

For subtasks 1 and 2 one can compute the answer in **O(N)** time. For subtask 3 one needs to compute (K-1)^{N-1} (modulo 10^9+7) using fast modular exponentiation, in **O(log(N))** time.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.