ROOMALLOC

The students of a school class are planning their five-day trip. The class consists of ~N~ students numbered from ~1~ to ~N~. The hotel they will stay at has ~K~ rooms, numbered from ~1~ to ~K~. Each student will be assigned to one of these rooms.

As you may know, on school trips students are more interested in staying with their friends - they are not particularly concerned about the capacity of the rooms. Therefore, in this problem, we assume that all students can fit into the same room.

The personal relationships among the students are complex. Some students have exactly one other student whom they dislike, and they will not end up in the same room as that student.

Your task is to find out how many different ways the students can be assigned to rooms. Two assignments are considered different if at least one student ends up in a different room.

Input:

The first line of the input will contain two positive integers ~N~ and ~K~, separated by a single space: the number of students and the number of rooms, respectively. The next line will contain ~N~ integers ~F_1~, ~F_2~, ..., ~F_N~, separated in pairs by spaces, such that ~1 \le F_i \le N~. If ~F_i = j \neq i~, it means that student ~i~ dislikes student ~j~ and will not end up in the same room as them. If ~F_i = i~, it means that student ~i~ does not dislike any other student.

Output:

The output must contain one line with exactly one integer: the number of possible ways the students can end up in the rooms. Since this number can be very large, you should print its remainder when divided (modulo) by the number ~10^9 + 7~.

Constraints:

• ~1 \le N,\;K \le 1.000.000~
• Time Limit: ~1~ sec.
• Memory Limit: ~64~ MB.
• For test cases with a total value of ~30%~, it will be ~1 \le N,\;K \le 10~.
• For test cases with a total value of ~60%~, it will be ~1 \le N \le 1000~ and ~1 \le K \le 20~.
• For test cases with a total value of ~59%~, the numbers ~F_i~ will all be distinct.

Examples of input - output:

1st

input:

2 3
2 1

output:

6

Explanation of the first example:

There are ~2~ students and ~3~ rooms available. Since the students dislike each other, they must go to different rooms. The possible assignments are: ~(1,\;2)~, ~(1,\;3)~, ~(2,\;1)~, ~(2,\;3)~, ~(3,\;1)~, ~(3,\;2)~, where the numbers inside the parentheses represent the rooms assigned to the two students, respectively.

2nd

input:

3 4
2 3 1

output:

24

3d

input:

3 4
2 1 1

output:

36