 # Book Coloring

#### Mirko wants to know the number of possible ways to color Slavko’s coloring book and he desperately needs your help! Calculate the number of possible ways to color the book. Given the fact that the output can be very large, print the answer modulo 1000000007.

##### Input Format:
``````The first line of input contains positive integers N, K.
Following line contains N numbers fi, the number stated in the text.
``````
##### Constraints:
``````1 ≤ N ≤ 1000000
1 ≤ K ≤ 1000000
1 ≤ fi ≤ N
Time limit = 1 sec
``````
##### Output Format:
``````The first and only line must contain the number of possible ways to color Slavko's book.
``````
##### Sample Input 1:
``````2 3
2 1
``````
##### Sample Output 1:
``````6
``````
##### Sample Input 2:
``````3 4
2 3 1
``````
##### Sample Output 2:
`````` 24
``````
##### Explanation:
``````For Sample Input 1:
Mirko has three colors and decided that the image numbered 2 mustn't be of the same color as the image numbered 1. The possible colorings are (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), where the first number in the brackets represents the color of the first image and the second number the color of the second image.``````