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._minhduc biết bạn thân 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\).

Mỗi trang shiba sẽ vẽ một màu duy nhất trong \(m\) màu có trong hộp bút. 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ì shiba có thể tô màu bất kì miễn là màu đó có trong hộp màu.

Yêu cầu: 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 _minhduc tặng. Bạn hãy giúp shiba đếm số cách mà anh ấy có thể tô.

Input

• 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)\).
• 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)\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Example

3 4
2 1 2

36