from collections import defaultdict

mod = 1234567891

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

dp = [0] * (sum(A)+10)
dp[0] = 1

while M:

    dp += [0] * len(dp)
    
    for a in A:
        for i in range(len(dp)-a-1,-1,-1):
            if i+a < len(dp):
                dp[i+a] += dp[i]
                dp[i+a] %= mod

    dp = dp[M%2::2]
    M //= 2

    # print (dp)
print (dp[0] % mod)