#include <bits/stdc++.h>

using namespace std;




#define ls o<<1
#define rs o<<1|1
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=2e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);


int n;
ll m;
ll a[45];


inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if (x == 0) {
        putchar('0');
        return;
    }
    char F[200];
    int tmp = x > 0 ? x : -x;
    if (x < 0)putchar('-');
    int cnt = 0;
    while (tmp > 0){
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)putchar(F[--cnt]);
}
map<ll,ll> mp[2];
void dfs(int pos,int r,ll now,int op){
    if(pos==r+1){
        mp[op][now]++;
        return ;
    }
    dfs(pos+1,r,now,op);
    if(now+a[pos]<=m)
    dfs(pos+1,r,now+a[pos],op);
}
void solve(){
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++){
        // scanf("%lld",&a[i]);
        a[i]=read();
    }
    if(n<=20){
        dfs(1,n,0,0);
        ll ans=0;
        for(auto it=mp[0].begin();it!=mp[0].end();it++){
            ans+=it->se;
        }
        printf("%lld\n",ans);
        return ;
    }
    dfs(1,n/2,0,0);
    dfs(n/2+1,n,0,1);
    ll last=0;
    vector<pll> ve;
    for(auto it=mp[1].begin();it!=mp[1].end();it++){
        ve.push_back({it->fi,it->se+last});
        last=ve.back().se;
    }
    ll ans=0;
    int rx=ve.size()-1;
    for(auto it=mp[0].begin();it!=mp[0].end();it++){
        ll tmp=m-(it->fi);
        while(rx>=0&&ve[rx].fi>tmp) rx--;
        if(rx>=0) ans+=ve[rx].se*(it->se);
        else break;
    }
    printf("%lld\n",ans);
}
int main(){
    // clock_t t1=clock();
	#ifndef ONLINE_JUDGE
       freopen("in.in", "r", stdin);
       freopen("out.out","w",stdout);
    #endif 
	// int T;scanf("%d",&T);while(T--)
	solve();
// end:
    // cerr<<"Time used "<<clock()-t1<<" ms"<<endl;
	return 0;
}