#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1234567891ll; int main() { ll N, M; cin >> N >> M; vector<int> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } vector<ll> dp(61000); dp[0] = 1; while (M) { for (int i = 0; i < N; i++) { for (int x = 60000; x >= 0; x--) { (dp[x + A[i]] += dp[x]) %= mod; } } for (int i = 0; i < 30000; i++) { dp[i] = dp[i * 2 + M % 2ll]; } fill(dp.begin() + 30000, dp.end(), 0ll); M >>= 1; } cout << dp[0] << endl; }