Madam C.J. Walker's Business Plan

There are n distinct items that you can buy and resell. Item i (indices start at 0) costs cost[i], and reselling it yields a profit of 2^i. You have x units of money, each item can be bought at most once, and the total cost of the items bought cannot exceed x. Find the maximum profit you can make. The answer may be large, so output it modulo 10^9+7.

输入格式

The first line contains two integers n and x; the second line contains n integers cost[0..n−1]. 1≤n≤100000, 1≤cost[i]≤10^9, 1≤x≤10^14.

输出格式

Output one integer: the maximum profit modulo 10^9+7.

样例 1

输入：

5 70
10 20 14 40 50

输出：

20

样例 2

输入：

2 7
3 4

输出：

3

样例 3

输入：

3 2
1 1 9

输出：

3

样例说明

Example 1: cost=[10,20,14,40,50], x=70. Buying 0,1,2 (cost 44) gives profit 7; 0 and 4 (cost 60) give profit 17; 1 and 4 (cost 70) give profit 18; 2 and 4 (cost 64) give profit 20, which is the maximum. Example 2: buying both items spends exactly 7, for a profit of 1+2=3. Example 3: the item at index 2 is unaffordable; buying the items at indices 0 and 1 gives a profit of 3.