import sys
input = sys.stdin.readline

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

mod=1234567891
DP=[0]*50001
DP[0]=1

for i in range(65):
    for a in A:
        for j in range(50000,-1,-1):
            if j+a<50001:
                DP[j+a]=(DP[j+a]+DP[j])%mod

    #print(DP[:50],M)

    if M%2==0:
        for j in range(0,50001):
            if j%2==0:
                DP[j//2]=DP[j]
                if j!=0:
                    DP[j]=0
            else:
                DP[j]=0
    else:
        for j in range(0,50001):
            if j%2==1:
                DP[j//2]=DP[j]
                DP[j]=0
            else:
                DP[j]=0

    #print(DP[:50])
    M//=2

print(DP[0])