Bạn được cho một chiếc máy nghe nhạc loại cũ của thập niên 90 với chất lượng âm thanh siêu đỉnh. Hiện tại bạn có ~n~ bài nhạc, bài nhạc thứ ~i~ có độ dài là ~a_i~ phút. Máy nghe nhạc mà bạn được cho ghi được tối đa ~m~ phút.

Yêu cầu: Hỏi có bao nhiêu cách ghi nhạc khác nhau lên máy nghe nhạc, biết rằng mỗi bài nhạc chỉ được phép ghi đúng một lần lên máy? Biết rằng cách ghi nhạc A khác cách ghi nhạc B khi số lượng bài nhạc trong hai cách là khác nhau hoặc trong cách ghi nhạc A khác cách ghi nhạc B ở cùng một vị trí thứ ~i~ bất kì.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n, m~ (~1 \le n, m \le 1000~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 1000~).

Output

• Một số nguyên duy nhất là số cách ghi nhạc lên máy. Do kết quả có thể rất lớn, bạn chỉ cần đưa ra kết quả chia lấy phần dư cho ~10^9 + 7~.

Sample Input 1

3 4
1 5 6

Sample Output 1

1