#include <cstdio>
#include <algorithm>

using namespace std;

const int mod = 1234567891;
long long dt[80001];
int a[50];

int main() {
  int n;
  long long m;
  scanf("%d%lld",&n,&m);
  for (int i = 0; i < n; i++) scanf("%d",&a[i]);
  int sum = accumulate(a,a+n,0);
  dt[0] = 1;
  while(m) {
    for (int i = 0; i < n; i++) for (int j = sum*2; j >= a[i]; j--) dt[j] = (dt[j] + dt[j-a[i]]) % mod;
    for (int i = 0; i <= sum; i++) dt[i] = dt[i*2+m%2];
    for (int i = sum+1; i <= sum*2; i++) dt[i] = 0;
    m /= 2;
  }
  printf("%lld\n", dt[0]);
  return 0;
}