Competitions

# Trees: Depth First Search

# Virus Tree 2

You are given a tree with **n** vertices and **n** − **1** edges. The vertices are numbered **1** to **n**, and the **i**-th edge connects vertices `a`

and _{i}`b`

._{i}

You have coloring materials of **k** colors. For each vertex in the tree, you will choose one of the **k** colors to paint it, so that the following condition is satisfied:

- If the distance between two different vertices
**x**and**y**is less than or equal to two,**x**and**y**have different colors.

How many ways are there to paint the tree? Find the count modulo `10`

+ ^{9}**7**.

#### Input

The first line contains two numbers **n** and **k**. Each of the next **n** - **1** lines contains two integers `a`

and _{i}`b`

._{i}

#### Output

Print the number of ways to paint the tree, modulo `10`

+ ^{9}**7**.

Input example #1

4 3 1 2 2 3 3 4

Output example #1

6

Input example #2

5 4 1 2 1 3 1 4 4 5

Output example #2

48