Cho mảng ~N~ số nguyên dương. Hãy đếm số lượng tập con (có thể rỗng) của mảng sao cho tổng các phần tử trong tập con đúng bằng ~K~.

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

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~K~ (~1 \le N \le 100~, ~1 \le K \le 10000~).
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ (~1 \le a_i \le 100~).

Output

In ra một số nguyên duy nhất là số lượng tập con có tổng bằng ~K~, lấy modulo ~10^9 + 7~.

Ví dụ

Input 1

5 5
1 2 3 4 5

Output 1

3

Giải thích 1

Ba tập con có tổng bằng ~5~ là: ~\{5\}~, ~\{1, 4\}~, ~\{2, 3\}~.

Input 2

3 10
5 5 5

Output 2

3

Giải thích 2

Ba tập con có tổng bằng ~10~ là: ~\{5_1, 5_2\}~, ~\{5_1, 5_3\}~, ~\{5_2, 5_3\}~.

Giới hạn