Có \(N\) đứa trẻ, được đánh số \(1,2,\cdots,N\)
\(Kaninho\) quyết định đem \(K\) viên kẹo chia cho \(N\) đứa trẻ này. Ở đây, với mỗi \(i(1 \leq i \leq N)\), đứa trẻ thứ \(i\) được nhận \(x\) viên kẹo với \(x \in [0;a_i]\). Biết rằng, \(Kaninho\) chia hết tất cả \(K\) viên kẹo cho \(N\) đứa trẻ này, không để lại viên nào.

Tìm số cách mà \(Kaninho\) có thể chia hết tất cả \(K\) viên kẹo cho \(N\) đứa trẻ này. Vì đáp án có thể lớn nên trước khi in ra ta cần lấy \(mod\) \(10^9+7\). Ở đây, hai cách chia được coi là khác nhau khi tồn tại một đứa trẻ nhận một số lượng kẹo khác nhau.

Input

• Dòng thứ nhất chứa hai số nguyên \(N\),\(K(1 \leq N \leq 100,0 \leq K \leq 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\cdots,a_N(0 \leq a_i \leq K)\)

Output

• In ra đáp án cần tìm.

Example

3 4
1 2 3 

5