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
    adds = [ a * nbit for a in A ]

    for add in adds:

        snapshot = list(dp.items())

        for s,v in snapshot:
            if s+add > M:
                continue
            dp[s+add] += v
            dp[s+add] %= mod
        
    ndp = defaultdict(int)
    mask = (2**(bit+1))-1
    for k in dp:
        if (k&mask) == (M&mask) and k <= M:
            ndp[k] = dp[k]
    dp = ndp

    # print (dp)

print (dp[M])