/**
 *    author:  zjs
 *    created: 08.05.2026 16:52:47
**/
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    unsigned long long m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    const int mod = 1234567891;

    int s = accumulate(a.begin(), a.end(), 0);
    vector<long long> carry(2 * s);
    carry[0] = 1;

    int len = bit_width(m);
    for (int b = 0; b < len; b++) {
        int bit = m >> b & 1;
        // 01背包
        for (int x : a) {
            for (int i = 2 * s - 1; i >= x; i--)
                carry[i] = (carry[i] + carry[i - x]) % mod; 
        }
        // 进位
        for (int i = 0; i < s; i++)
            carry[i] = carry[2 * i + bit];
        for (int i = s; i < 2 * s; i++)
            carry[i] = 0;
    }
    cout << carry[0] << '\n';
}