Cô bé Mirko dành thời gian rảnh để vẽ tranh. Với sở thích này, anh ấy thích sử dụng cọ vẽ và một bảng màu tổng thể có ~K~ màu. Người bạn Slavko của anh quyết định sử dụng tài năng của Mirko và đưa cho anh cuốn sách tô màu mới để Mirko tô màu. Cuốn sách tô màu chứa ~N~ hình ảnh được đánh số ~1, 2, ..., N~.

Mirko đã quyết định vẽ mỗi hình ảnh bằng chính xác một màu trong số ~K~ màu có thể có từ bảng màu của mình. Tuy nhiên, anh ấy thực sự thích những thứ đầy màu sắc. Anh ta chọn ~N~ số ~f_i~ và quyết định vẽ ảnh đánh số ~i~ khác với các ảnh đánh số ~f_i~, ngoại trừ khi ~f_i = i~. Nếu ~f_i = i~, điều đó có nghĩa là anh ta có thể vẽ hình ảnh được đánh số ~f_i~ bất kỳ màu nào anh ta thích, miễn là tất cả các điều kiện khác đều được đáp ứng. Mirko muốn biết số cách có thể để tô màu cuốn sách tô màu của Slavko và anh ấy rất cần sự giúp đỡ của bạn! Tính số cách tô màu cuốn sách. Với thực tế là đầu ra có thể rất lớn, hãy in kết quả theo modulo ~1 000 000 007~.

Input

• Dòng đầu tiên chứa các số nguyên dương ~N~, ~K~ ~(1 \le N, K \le 1 000 000)~.
• Dòng tiếp theo chứa ~N~ số ~f_i~ ~(1 \le f_i \le N)~, số được nêu trong đoạn văn.

Output

• Dòng đầu tiên và duy nhất phải chứa số cách có thể tô màu cho cuốn sách của Slavko.

Scoring

• Trong dữ liệu kiểm tra có giá trị 50% tổng số điểm, tất cả các số ~f_i~ sẽ khác.

Sample Input 1

2 3
2 1

Sample Output 1

6

Sample Input 2

3 4
2 3 1

Sample Output 2

24

Sample Input 3

3 4
2 1 1

Sample Output 3

36

Sample Input 4

3 4
1 1 2

Sample Output 4

36

Làm rõ ví dụ đầu tiên:

• Mirko có ba màu và quyết định rằng hình ảnh được đánh số ~2~ không được cùng màu với hình ảnh được đánh số ~1~. Các màu có thể có là ~(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)~, trong đó số đầu tiên trong ngoặc biểu thị màu của hình ảnh đầu tiên và số thứ hai là màu của hình ảnh thứ hai.

Làm rõ ví dụ thứ tư:

• Mirko có bốn màu. Không có điều kiện nào liên quan đến hình ảnh đầu tiên, nó có thể được sơn bằng bất kỳ màu nào. Cái thứ hai phải khác cái thứ nhất, cái thứ ba phải khác cái thứ hai. Nghĩa là ~2~ ảnh đó có thể tô bằng ~3~ màu còn lại. Điều này cho chúng ta tổng cộng ~36~ kết hợp.