#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() #define yes cout << "Yes" << "\n" #define no cout << "No" << "\n" #define pb push_back #define F first #define S second #define mp make_pair typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef vector <pii> vii; typedef vector <ll> vi; template<typename T> void read(vector<T>& v) { for (auto &x : v) cin >> x; } template<typename T> void print(const vector<T>& v) { for (auto &x : v) cout << x << ' '; cout << "\n"; } const ll MAX = 1e6 + 5; const ll MOD = 1e9 + 7; ll dp[MAX]; void solve() { ll n, m; cin >> n >> m; vi a(n); read(a); if (m <= 1e6) { dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = m; j >= a[i]; j--) { dp[j] += dp[j - a[i]]; } } ll cem = 0; for (int i = 0; i <= m; i++) { cem += dp[i]; } cout << cem << "\n"; } else { ll say = 0; for (ll mask = 0; mask < (1 << n); mask++) { ll cem = 0; for (ll i = 0; i < n; i++) { if ((1 << i) & mask) { cem += a[i]; } } if (cem <= m) { say++; } } cout << say << "\n"; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for (int i = 1; i <= t; i++) { solve(); } }