Trong chuyện cổ tích cây khế, con chim ăn khế và trả vàng cho người em.

Chim chở người em đến chỗ chứa vàng, ở đó có n cục vàng. Cục thứ \(i\) có khối lượng là \(m_i\).

Túi ba gang có sức chứa là \(M\), hãy đếm xem có bao nhiêu cách để người em chọn các cục vàng để lấy. Hai cách lấy được coi là khác nhau nếu tồn tại \(i\) sao cho ở cách lấy này có lấy cục thứ \(i\) còn ở cách kia thì không.

Input

• Dòng 1: \(n, M\)
• Dòng 2: \(m_1, m_2,. . . ,m_n\)

Output

• Ghi ra một số duy nhất là kết quả tìm được.

Scoring

• \(n \le 40\) ; \(1 \le m_i\) , \(M \le 10^6\)
• Subtask \(1\) (\(50\%\) số điểm): \(n \le 20\)

Example

4 10
3 10 5 4

8