COCI '13 Contest 2 #5 Paleta

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

Little Mirko spends his free time painting. For this hobby, he likes to use brushes and a pallet containing K colors overall. His friend Slavko decided to use Mirko's talent and gave him his new coloring book for Mirko to color. The coloring book contains N images numbered 1, 2, ..., N.

Mirko has decided to paint each image in exactly one color of the possible K colors from his pallet. However, he really likes colorful things. He chose N numbers f_i and decided to paint the image numbered i differently than the images numbered f_i, except when f_i = i. If f_i = i, that means he can paint the image numbered f_i whichever color he likes, as long as all other conditions have been met.

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 1\,000\,000\,007.


The first line of input contains positive integers N, K (1 \le N, K \le 1\,000\,000).

Following line contains N numbers f_i (1 \le f_i \le N), the number stated in the text.


The first and only line must contain the number of possible ways to color Slavko's book.


In test data worth 50\% of total points, all numbers f_i will be different.

Sample Input 1

2 3
2 1

Sample Output 1


Explanation for Sample Output 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.

Sample Input 2

3 4
2 3 1

Sample Output 2


Sample Input 3

3 4
2 1 1

Sample Output 3


Sample Input 4

3 4
1 1 2

Sample Output 4


Explanation for Sample Output 4

Mirko has four colors. There are no conditions regarding the first image, it can be painted in whichever color. The second must be different than the first, and the third different than the second. That means that those two images can be colored in the remaining 3 colors. This gives us a total of 36 combinations.


There are no comments at the moment.