#include <bits/stdc++.h> using namespace std; namespace { typedef double real; typedef long long ll; template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) { if (vs.empty()) return os << "[]"; os << "[" << vs[0]; for (int i = 1; i < vs.size(); i++) os << " " << vs[i]; return os << "]"; } template<class T> istream& operator>>(istream& is, vector<T>& vs) { for (auto it = vs.begin(); it != vs.end(); it++) is >> *it; return is; } int N; ll M; vector<int> A; void input() { cin >> N >> M; A.resize(N); cin >> A; } const ll MOD = 1234567891LL; void solve() { vector<ll> g(1000*N + 1, 0); g[0] = 1; for (int i = 0; i < N; i++) { for (int j = 1000*N; j >= 0; j--) { if (j - A[i] >= 0) g[j] = (g[j] + g[j - A[i]]) % MOD; } } vector<vector<ll>> f(61, vector<ll>(1000*N + 1, 0)); for (ll x = 0; x <= 1000*N; x++) { if ( (x & 1LL) == (M & 1LL) ) { f[0][x] = g[x]; } } for (int p = 1; p <= 60; p++) { vector<vector<ll>> h(N + 1, vector<ll>(1000*N + 1, 0)); for (ll x = 0; x <= 1000*N; x++) { h[0][x/2] += f[p - 1][x]; } for (int k = 1; k <= N; k++) { for (ll x = 0; x <= 1000*N; x++) { h[k][x] = h[k - 1][x]; if (x - A[k-1] >= 0) h[k][x] = (h[k][x] + h[k-1][x - A[k-1]]) % MOD; } } for (ll x = 0; x <= 1000*N; x++) { if ( (M & (1LL<<p)) == ((x & 1LL)<<p) ) { f[p][x] = h[N][x]; } } } /* for (int p = 0; p < 5; p++) { for (ll x = 0; x < 10; x++) { cout << f[p][x] << " "; } cout << endl; } */ cout << f[60][0] << endl; } } int main() { input(); solve(); return 0; }