from collections import defaultdict

mod = 1234567891

N,M = map(int,input().split())
A = list(map(int,input().split()))

dp = defaultdict(int)
dp[0] = 1

for bit in range(60):

    nbit = 2**bit

    for i in range(N):

        add = (nbit * A[i])
        
        keys = list(dp.keys())
        keys.sort()
        keys.reverse()

        ndp = defaultdict(int)

        for k in keys:
            ndp[k] = (ndp[k] + dp[k]) % mod
            ndp[k+add] = (ndp[k+add] + dp[k]) % mod

        dp = ndp
        
    ndp = defaultdict(int)
    for k in dp:
        if k % nbit == M % nbit and k <= M:
            ndp[k] = dp[k]
    dp = ndp

    # print (dp)

print (dp[M])