Наконец, Иван был принят в университет! После изнурительного года подготовки к вступительным экзаменам он был настроен на большой перерыв. К сожалению, летние каникулы были короткими, и ему было недостаточно отдыха, но он не разочаровался. Иван слышал, что, когда пребывая в университете, не обязательно следить за каждой лекцией. Он решил продлить свой отпуск, хотя начался учебный год. Так он и сделал!

Но, конечно, для каждого плюса есть минус - так же как и в средних школах, в каждом колледже или университете есть экзамены. Точнее, в учебном плане Ивана имеется в точности n экзаменов. Они могут различаться по сложности, и поэтому два экзамена могут давать разные баллы. Иван не обязан сдавать экзамены, но очки, набранные за тесты, важны для него, потому что они являются частью его окончательной оценки. Он быстро понял, что ему нужно, по крайней мере, t балов ото всех экзаменов, чтобы иметь хорошую оценку. Он уверен, что после всех экзаменов он сможет набрать не менее t балов, но он подозревает, что могут быть разные способы сделать это. Чем больше способов, тем больше свободного времени у него есть - Иван сможет выбрать, какой экзамен взять и чего не делать. Таким образом, он решит, как распределить свой досуг - например, какие концерты или футбольные матчи посетить. На самом деле Иван полностью уверен в своих способностях, поэтому, если он сдаст экзамен, он получит полный балл. Не позволяйте Ивану думать о том, сколькими способами он сможет собрать не менее t баллов, но напишите программу которая сделает это за него.

Входные данные

Первая строка содержит два натуральных числа n (n ≤ 36) и t. Следующая строка содержит n натуральных чисел, задающих количество балов для каждого экзамена. Каждое число во второй строке не более 1013.

Выходные данные

Выведите одно число - количество вариантов, которыми Иван может выбрать какие экзамены сдавать или нет, так чтобы сумма набранных балов была как минимум t.

Объяснение

Существует девять способов которыми Иван может выбрать какие экзамены сдавать так чтобы набрать хотя бы 6 балов: (первый и третий); (второй и третий); (первый, второй и третий); (второй и четвертый); (первый, второй и четвертый); (первый, третий и четвертый); (второй, третий и четвертый); (первый, второй, третий и четвертый); (третий и четвертый).