#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair i_i; typedef pair ll_i; typedef pair d_i; typedef pair ll_ll; typedef pair d_d; struct edge { ll B, T, F, P; }; ll MOD = 1234567891; ll _MOD = 1000000009; double EPS = 1e-10; int INF = INT_MAX / 10; int main() { int N; ll M; cin >> N >> M; vector A(N); for (int i = 0; i < N; i++) cin >> A[i]; vector dp(50000); dp[0] = 1; for (; M > 0; M /= 2) { for (int i = 0; i < N; i++) for (int j = 49999; j - A[i] >= 0; j--) dp[j] = (dp[j] + dp[j - A[i]]) % MOD; for (int j = 0; j < 25000; j++) dp[j] = dp[j * 2 + M % 2]; for (int j = 25000; j < 50000; j++) dp[j] = 0; } cout << dp[0] << endl; }