#include<iostream>
#include<algorithm>
#include<climits>
#include<cstring>
#include<fstream>
#include<vector>
#define all(a) a.begin(), a.end()
#define fr(i, zz, zzz) for (int i = zz; i <= zzz; i++)
#define ll long long
#define pii pair<int, int>
#define frr(i, zz, zzz) for (int i = zz; i >= zzz; i--)
#define full(asdf) memset(asdf, 0, sizeof(asdf))
#define st first
#define nd second
#define IOS ios_base::sync_with_stdio(0);   cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1E6+1;
int a[5005], n, k;
ll c[N], mn = LLONG_MAX;
vector<ll> res, ress;
void Try(int i, int en, int sum, vector<ll>& p) {
	if (sum + (en - i)*mn > k)
		return;	
	if (i > en) {
		p.push_back(sum);
		return;
	}
	
	else  {
		Try(i+1, en, sum + a[i], p);
		Try(i+1, en, sum, p);
	}
}
int main () {
	IOS
	fstream f,g;
	f.open("FAIR.INP", ios::in);
	g.open("FAIR.OUT", ios::out);
	int cnt = 0;
	f >> n >> k;
	fr(i, 1, n) {
		f >> a[i]; 
		mn = min(mn, (ll)a[i]);
		}
	if (k == 0) {
		g << 1;
		return 0;
	}
	if (n <= 40) {
	Try(1, n/2, 0, res);
	Try(n/2+1, n, 0, ress);
/*	
	for (int x : res)
		cout << x << " ";
	cout << "\n";
	for (int x : ress)
		cout << x << " ";
	cout << "\n";
	*/
	fr(i, 0, res.size() - 1) {
		if (res[i] != -1) {
			if (res[i] == k) {
				++cnt;
				res[i] = -1;
			}
			else {
				fr(j, 0, ress.size() - 1) {
					if (ress[j] != -1) {
						if (ress[j] == k) {
							++cnt;
							ress[j] = -1;
						}
						else {
							if (res[i] + ress[j] == k) {
								++cnt;
							}
						}
					}
				}
			}
		}
	}
	g << cnt % 123456789;
	return 0;
	}
	else {	
		ll s = 0;
		full(c);
		c[0] = 1;
		fr(i, 1, n) {
			if (s + a[i] < k) 
				s += a[i];
			else
				s = k;
			frr(j, s, a[i]) {
				if (c[j - a[i]] != 0) 
					c[j] = (c[j] + c[j - a[i]]) % 123456789;
			}
		}
		g << c[k];
	}
}