Đất nước Babylon cổ đại đã quyết định xây dựng một tòa tháp khổng lồ. Tòa tháp gồm N khối đá được xếp chồng lên nhau. Họ đã quy tụ được nhiều khối đá dạng hình vuông có kích cỡ khác nhau trên khắp đất nước. Theo kinh nghiệm xây dựng lâu năm họ đã đúc kết ra rằng: Nếu đặt một khối đá trực tiếp trên lên khối đã nhỏ hơn nhiều, tòa tháp sẽ đỗ.

Mỗi khối đá là khác nhau và có thể có cùng kích thước. Theo kinh nghiệm, các kỹ thuật viên đã đưa ra một số nguyên D với ý nghĩa: không được đặt khối đá A trực tiếp lên trên khối đá B nếu diện tích mặt của A là lớn hơn diện tích mặt của B + D.

Yêu cầu: Hãy tính số cách khác nhau để xây dựng tòa tháp mà trong đó sử dụng tất cả các khối đá hiện có. Vì con số này có thể là rất lớn nên kết quả đưa ra sau khi chia lấy phần dư cho 10^9+9.

Dữ liệu vào:

• Dòng 1: Chứa hai số nguyên N và D (1 ≤ N ≤ 106; 1 ≤ D ≤ 109).

• Dòng 2: Chứa N số nguyên, số thứ i là diện tích mặt của khối đá thứ i, các số này thuộc phạm vi [1..109].

Kết quả ra:

ghi một số nguyên duy nhất là số cách khác nhau để xây dựng tòa tháp, số này được đưa ra với phép chia lấy phần dư cho 10^9+9.

Sample Input

4 1
1 2 3 100

Sample Output

4

Giải thích

ta có 4 cách: 100+1+2+3; 100+2+3+1; 100+3+1+2; 100+3+2+1.
Ràng buộc: 
•   20% test với N ≤ 20
•   50% test với  N ≤ 1000.
•   100% test với N ≤ 10^6.