Đ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. 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.

Input

Dòng đầu tiên chứa hai số nguyên n và m (~1 \leq n \leq 300 000~, ~2 \leq m \leq 10^{9}~ ), 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 \leq a_{i} \leq 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.

Output

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~.

Sample Input

4 1000
2 1 10 2

Sample Output

5

Note

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)~.