Giải bài trực tuyến

Đa tập hợp (multiset) là một cấu trúc toán học tương tự như tập hợp, nhưng mỗi phần tử của một đa tập hợp có thể xuất hiện nhiều lần. Tương tự như tập hợp, các phần tử của một đa tập hợp có thể được sắp xếp theo nhiều cách khác nhau. Chúng ta gọi mỗi cách sắp xếp là một hoán vị của đa tập hợp. Ví dụ, trong số các hoán vị của đa tập hợp {1,1,2,3,3,3,7,8} thì có (2,3,1,3,3,7,1,8) và (8,7,3,3,3,2,1,1).

Ta nói hoán vị của một đa tập hợp có thứ tự từ điển nhỏ hơn một hoán vị khác nếu phần tử ở vị trí đầu tiên mà hai hoán vị khác nhau của hoán vị thứ nhất có giá trị nhỏ hơn của hoán vị thứ hai. Tất cả các hoán vị của một đa tập hợp cho trước có thể được đánh số theo thứ tự từ điển tăng dần bắt đầu từ 1.

Yêu cầu

Viết chương trình đọc vào một hoán vị của một đa tập hợp và một số nguyên dương m, xác định phần dư của thứ tự của hoán vị đó khi chia cho m.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên n và m (1 ≤ n ≤ 300 000, 2 ≤ m ≤ 10⁹), cách nhau bởi khoảng trắng cho biết kích thước của đa tập hợp và số m. Dòng thứ hai chứa n số nguyên dương a_i (1 ≤ a_i ≤ 300 000) cách nhau bởi khoảng trắng thể hiện một hoán vị của đa tập hợp.

Kết quả

In ra một số nguyên duy nhất là phần dư của thứ tự của hoán vị khi chia cho m.

Ví dụ

Dữ liệu
4 1000 
2 1 10 2 

Kết quả
5

Các hoán vị nhỏ hơn (theo thứ tự từ điển) hoán vị đã cho là (1,2,2,10), (1,2,10,2), (1,10,2,2) và (2,1,2,10).