Trong một kỳ thi lập trình thi đấu theo thể thức đồng đội, tại mọi thời điểm các đội đều có thứ hạng đôi một khác nhau; đội đứng đầu có thứ hạng ~1~.

Một thành viên của đội rời khỏi phòng thi trong một khoảng thời gian. Khi quay lại, người đó thấy đội mình đang đứng hạng ~K~. Đồng đội cho biết rằng trong thời gian vừa qua có ~N~ đội đã vượt qua đội mình, và đưa ra danh sách ~a_1,a_2,\ldots,a_N~, trong đó ~a_i~ là thứ hạng của đội thứ ~i~ tại thời điểm người đó rời khỏi phòng.

Trong khoảng thời gian này, đội của bạn không vượt qua đội nào khác. Mỗi khi một đội vượt qua đội của bạn, thứ hạng của đội bạn tăng thêm ~1~.

Tuy nhiên, một số thông tin trong danh sách trên có thể không chính xác. Bạn được phép gạch bỏ một số phần tử bất kỳ trong danh sách, có thể không gạch phần tử nào hoặc gạch bỏ tất cả.

Sau khi gạch bỏ, báo cáo được gọi là \emph{hợp lệ} nếu có thể xảy ra một diễn biến thứ hạng phù hợp với tất cả các thông tin còn lại: chính xác các đội còn lại trong danh sách đã vượt qua đội của bạn, và cuối cùng đội của bạn đứng hạng ~K~.

Yêu cầu: Hãy tính số cách gạch bỏ các phần tử để báo cáo còn lại là hợp lệ.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ (~1\le N\le 2\cdot10^5~, ~1\le K\le 10^9~).

Dòng thứ hai chứa ~N~ số nguyên dương ~a_1,a_2,\ldots,a_N~ (~1\le a_i\le10^9~), là thứ hạng ban đầu của các đội được báo cáo. Dữ liệu đảm bảo rằng các số ~a_1,a_2,\ldots,a_N~ đôi một phân biệt.

Output

In ra một số nguyên duy nhất --- số cách gạch bỏ để báo cáo còn lại là hợp lệ.

Do kết quả có thể rất lớn, hãy in kết quả modulo ~10^9+9~.

Sample input 1

1 2
2

Sample output 1

2

Giải thích

Có hai cách: gạch bỏ đội được báo cáo, hoặc giữ lại đội đó. Nếu giữ lại, trước khi bị vượt đội của bạn đứng hạng ~1~, còn đội được báo cáo đứng hạng ~2~, nên việc đội này vượt qua là có thể xảy ra.

Sample input 2

1 2
1

Sample output 2

1

Giải thích

Nếu giữ lại đội được báo cáo thì trước khi bị vượt, cả hai đội đều phải đứng hạng ~1~, điều này là không thể. Vì vậy chỉ có cách gạch bỏ đội đó.

Sample input 3

 3 4
 3 5 7

Sample output 3

7