Marisa có \(n\) kệ sách, kệ thứ \(i\) có \(A_i\) cuốn sách.

Cô muốn lấy ra \(k\) quyển để đọc. Mỗi kệ sách, cô sẽ không lấy quá \(1\) quyển. Hỏi có bao nhiêu cách để lấy ra \(k\) cuốn sách?

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,k\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Output

• In ra một số nguyên, số lượng modulo \(10_9+7\)

Điều kiện

• \(1 \le k \le n \le 10^{3}\)
• \(1 \le A_i \le 10^{9}\)

Sample Input 1

3 2
1 2 1

Sample Output 1

5

Chú ý: Có \(5\) cách: \((1_1,2_1)\) \((1_1,2_2)\) \((1_1,3_1)\) \((2_1,3_1)\) \((2_2,3_1)\)