#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <math.h>
//#include <sys/resource.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const bool debug = true;
#define ff first
#define ss second
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define YN(x) if(x)yes; else no;
#define all(X) (X).begin(), (X).end()
#define rall(X) (X).rbegin(), (X).rend()
const int mod = 1e9 + 7;
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
static inline int __builtin_clz(unsigned int x) {
unsigned long leading_zero = 0;
if (_BitScanReverse(&leading_zero, x)) {
return 31 - leading_zero;
}
return 32;
}
static inline int __builtin_clzll(unsigned __int64 x) {
unsigned long leading_zero = 0;
if (_BitScanReverse64(&leading_zero, x)) {
return 63 - leading_zero;
}
return 64;
}
#endif
// void increaseStack(rlim_t stackSize) {
// struct rlimit rl;
// int result;
// result = getrlimit(RLIMIT_STACK, &rl);
// if (result == 0) {
// if (rl.rlim_cur < stackSize) {
// rl.rlim_cur = stackSize;
// result = setrlimit(RLIMIT_STACK, &rl);
// if (result != 0) {
// cerr << "Error setting stack size." << endl;
// }
// }
// }
// }
void print(long long t) { cerr << t; }
void print(int t) { cerr << t; }
void print(string t) { cerr << t; }
void print(char t) { cerr << t; }
void print(double t) { cerr << t; }
void print(long double t) { cerr << t; }
void print(unsigned long long t) { cerr << t; }
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[], V n) { cerr << "["; for (int i = 0; i < n; i++) { cerr << v[i] << " "; } cerr << "]"; }
template <class T, class V> void print(pair <T, V> p) { cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}"; }
template <class T> void print(vector <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(set <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(multiset <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void print(map <T, V> v) { cerr << "[ "; for (auto i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(queue <T> q) { cerr << "[ "; while (!q.empty()) { print(q.front()); cerr << " "; q.pop(); } cerr << "]"; }
template <class T> void print(priority_queue <T> q) { cerr << "[ "; while (!q.empty()) { print(q.top()); cerr << " "; q.pop(); } cerr << "]"; }
template <class T> void print(int n__, T arr[]) { cerr << "[ "; for (int i = 0; i <= n__; i++) { print(arr[i]); cerr << " "; } cerr << "]"; }
ll gcdll(ll a, ll b) { return b == 0 ? a : gcdll(b, a % b); }
long long binpow(long long a, long long b) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
struct Mint
{
static int m;
int v;
Mint(long long value = 0) {
v = value % m;
if (v < 0) v += m;
}
static void set_mod(int new_mod) { m = new_mod; }
friend istream& operator >> (istream& inp, Mint& a) {
ll x; inp >> x;
a = x; return inp;
}
friend ostream& operator << (ostream& out, const Mint& a) { out << a.v; return out; }
Mint& operator += (const Mint& o) { v += o.v; if (v >= m) v -= m; return *this; }
Mint& operator -= (const Mint& o) { v -= o.v; if (v < 0) v += m; return *this; }
Mint& operator *= (const Mint& o) { v = (long long)v * o.v % m; return *this; }
Mint pow(long long b) const {
Mint res = 1, a = *this;
while (b > 0) {
if (b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
Mint inv() const{
return pow(m - 2);
}
Mint& operator++() { v++; if (v == m) v = 0; return *this; }
Mint& operator--() { if (v == 0) v = m; --v; return *this; }
Mint& operator /= (const Mint& other) { return *this *= other.inv(); }
friend Mint operator + (const Mint& a, const Mint& b) { return Mint(a) += b; }
friend Mint operator - (const Mint& a, const Mint& b) { return Mint(a) -= b; }
friend Mint operator * (const Mint& a, const Mint& b) { return Mint(a) *= b; }
friend Mint operator / (const Mint& a, const Mint& b) { return Mint(a) /= b; }
friend bool operator == (const Mint& a, const Mint& b) { return a.v == b.v; }
friend bool operator != (const Mint& a, const Mint& b) { return a.v != b.v; }
Mint operator - () const { return Mint(m - v); }
};
int Mint::m = mod;
struct point
{
int x, y;
typedef point P;
point(int x = 0, int y = 0) : x(x), y(y) {};
friend istream& operator >> (istream& inp, P& a) {
int x1, y1; inp >> x1 >> y1;
a.x = x1;
a.y = y1;
return inp;
}
P operator+ (const P o)const {
return P(x + o.x, y + o.y);
}
P operator- (const P o)const {
return P(x - o.x, y - o.y);
}
P& operator+=(const point& o) {
x += o.x;
y += o.y;
return *this;
}
P& operator-=(const point& o) {
x -= o.x;
y -= o.y;
return *this;
}
bool operator==(const P o)const {
return { x == o.x && y == o.y };
}
bool operator!=(const P o)const {
return !(*this == o);
}
bool operator<(const P o)const {
return x < o.x || (x == o.x && y < o.y);
}
bool operator<=(const P o)const {
return (*this < o || *this == o);
}
bool operator>(const P o)const {
return !(*this <= o);
}
bool operator>=(const P o)const {
return !(*this < o);
}
ll dot(const P o) const {
return (1ll * x * o.x + 1ll * y * o.y);
}
ll cross(const P o)const {
return (1ll * x * o.y - 1ll * y * o.x);
}
ll len2() const {
return (1ll * x * x + 1ll * y * y);
}
ld len() const {
return sqrtl(1ll * x * x + 1ll * y * y);
}
ld dist(const P o) const {
return (o - *this).len();
}
ll dist2(const P o) const {
return (o - *this).len2();
}
};
const int LOG = 21;
const int N = 40 + 5;
const ll inf = 1e9;
ll a[N];
ll s[(1 << LOG)];
void solve()
{
int n;
ll m;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
s[0] = 0;
int L = n / 2;
vector<ll>vec;
vec.push_back(0ll);
ll answ = 0;
for (int mask = 1; mask < (1 << L); mask++)
{
int l = 31 - __builtin_clz(mask);
s[mask] = s[mask ^ (1 << l)] + a[l];
vec.push_back(s[mask]);
if (s[mask] <= m)
answ++;
}
sort(all(vec));
for (int mask = 1; mask < (1 << (n - L)); mask++)
{
int l = 31 - __builtin_clz(mask);
s[mask] = s[mask ^ (1 << l)] + a[L + 1 + l];
int ind = lower_bound(all(vec), m - s[mask]) - vec.begin();
answ += 1ll * ind;
}
cout << answ + 1ll;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
