Fantastic Necklace

Alice is one of the most famous necklace designers. She is designing a fantastic necklace of new styles. Like other necklaces, this necklace consists of n beads and n strings connecting the bead together. The most significant difference is that the beads are not connected one by one but has many branches. The branches connecting to the same bead can be arranged arbitrarily. The shaking of the branches makes the necklace more glaring. Another difference is that the beads are not connected with ordinary strings. The two ends of each string differ, which makes the necklace more unique.
She has finished the structure of the new necklace. However, she is hesitating what color of bead should be used for each position. As a famous designer, she has beads of m colors and each type has infinite number of beads. She wants to make a necklace that any pair of adjacent beads has different colors. Now can you tell her how many different necklaces can she make with the colorful beads? Two necklaces are counted as one if each bead coincides after rotating the necklace or rearranging the braches. But because of the special strings, two necklaces with mirroring arrangements are not considered the same.

The input consists of about 50 test cases. The first line of each test case contains two integers, n and m, the number of beads of the necklace and the number of colors of beads Alice has (2 < n ≤ 100000, 1 ≤ m ≤ 100000). The second line contains n integers, the i-th of which, named pi, means that there is a string from the i-th bead to the pi-th bead (1 ≤ p_i ≤ n and p_i does not equal to i). The necklace is always valid and there is no duplicated string connecting the same pair of beads.

For each test case, output the number of different necklaces that Alice can make in one line. For the answer is large, so please give the result of answer module 1,000,000,007.

3 3
2 3 1
3 2
2 3 1
6 3
2 3 1 1 2 3
6 2
2 3 4 1 1 3
6 3
2 3 1 1 4 4

2
0
16
2
36

2012 Asia ChangChun Regional Contest