{"code":"lqdojcontest10bai7","name":"LQDOJ Contest #10 - Bài 7 - Tô Màu","description":"[user:shiba] là một anh chàng rất thích vẽ tranh. Anh ấy sở hữu một hộp màu chứa $m$ màu khác nhau.[user:_minhduc] biết bạn thân [user:shiba] của mình rất thích vẽ nên đã tặng cho một cuốn sách có $n$ trang, mỗi trang được đánh số từ $1$ đến $n$.\r\n\r\nMỗi trang [user:shiba] sẽ vẽ một màu duy nhất trong $m$ màu có trong hộp bút. [user:shiba] quy định bức tranh trang thứ $a_i$ phải tô khác màu so với bức tranh trang thứ $i$. Có một trường hợp ngoại lệ đặc biệt là $a_i = i$. Nếu $a_i = i$ thì [user:shiba] có thể tô màu bất kì miễn là màu đó có trong hộp màu.\r\n\r\n**Yêu cầu:** [user:shiba] muốn biết rằng mình có mấy cách khác nhau để tô hết cuốn sách do [user:_minhduc] tặng. Bạn hãy giúp [user:shiba] đếm số cách mà anh ấy có thể tô.\r\n\r\n#### Input\r\n\r\n - Dòng đầu tiên chứa hai số nguyên dương lần lượt là $n$ và $m$ $(1 \\le n,m \\le 10^6)$.\r\n - Dòng tiếp theo chứa $n$ số nguyên dương $a_1,a_2,...,a_n$ $(1 \\le a_i \\le n)$.\r\n\r\n#### Output \r\n\r\n - In ra kết quả bài toán sau khi chia lấy dư cho $10^9+7$.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 4\r\n        2 1 2\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        36\r\n        ```","points":1900.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}