Bobo có các loại tiền với mệnh giá \(c_1, c_2, \dots, c_n\). Mỗi loại có thể dùng không giới hạn số lần.

Hãy đếm số cách dùng các đồng tiền để tạo thành tổng \(S\).

Chú ý: hai cách chỉ khác nhau thứ tự lấy tiền được coi là giống nhau (dùng startIdx để tránh trùng).

Input

Dòng đầu chứa \(n\) và \(S\) (\(1 \le n \le 15\), \(1 \le S \le 10^5\)).
Dòng hai chứa \(n\) mệnh giá \(c_i\) (\(1 \le c_i \le 10^4\)).

Output

In ra một số nguyên là số cách đổi tổng \(S\).

Example

3 10
2 3 5

Output:

4