Naruto went to watch a movie with his friends which turned out to be very boring. He decided to punish his friends with a problem for forcing him to watch such a boring movie.
There exists an array A consisting of N numbers. Output the number of subsets of the array A whose sum is greater than or equal to K.
Naruto's friends being quite weak in coding were not able to solve this problem. Can you solve it for them and save them from Naruto's Rasengan ?

INPUT FORMAT
The first line of input contains N which is the size of array A. The next line contains N numbers denoting the elements of array A. The third line contains the value K as described in the problem statement.

OUTPUT FORMAT
The output should contain a single value denoting the number of subsets of array A which have their sum greater than or equal to K.

CONSTRAINTS

• \(1 ≤ N ≤ 40\)
• \(1 ≤ A[i],K ≤ 10^{16}\)