Twoim zadaniem jest obliczenie liczby najdłuższych rosnących podciągów ciągu A modulo liczba m.

입력 형식

W pierwszej linii wejścia znajdują się dwie liczby całkowite n i m (1 ≤ n ≤ 500 000, 1 ≤ m ≤ 10⁹), odpowiednio długość ciągu A i liczba m. W następnym wierszu n liczb całkowitych - kolejne elementy ciągu A (0 ≤ a_i ≤ 10⁹) .

출력 형식

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczę całkowitą - liczba najdłuższych rosnących podciągów modulo m.

예제 입력

4 10
3 2 5 4

예제 출력

4