Meet in the middle#11431
An array of integers is given. In how many ways can you choose a subset of its elements such that their sum is equal to ?
The first line contains two integers: n~(1 \le n \le 40) — the size of the array, and s~(1 \le s \le 10^9) — the required sum.
The second line contains integers: t_1, t_2, \dots, t_n~(1 \le t_i \le 10^9) — the elements of the array.
Print a single integer — the number of ways to choose a subset of the array elements whose sum is equal to .
Example 1
Example 2