Max Profit

Find the maximum profit that can be generated for the given amount of money. As the answer can be rather large, report the answer as maxProfit % (10 ^ 9 + 7) where % denotes modulo operator. Function Description Complete the function maxProfit in the editor. maxProfit has the following parameters: int[] cost: an array of integers representing the cost of each item int x: the initial amount of money Walker has Returns int: the maximum profit that can be obtained modulo (10⁹+7)

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ cost[i] ≤ 10⁵
• 0 ≤ x ≤ 10⁹

Example 1

Input:

cost = [3, 4, 1]
x = 8

Output:

7

Explanation: :)

Example 2

Input:

cost = [19, 78, 27, 15, 20, 25]
x = 25

Output:

16

Explanation: :)

Example 3

Input:

cost = [10, 20, 14, 40, 50]
x = 70

Output:

20

Explanation: Some possible combination of items Walker can buy are: She can buy items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ^ 0 + 2 ^ 1 + 2 ^ 2 = 7 She can buy items 0 and 4 for a cost of 60 and obtain a profit of 2 ^ 0 + 2 ^ 4 = 17 She can buy items 1 and 4 for a cost of 70 and obtain a profit of 2 ^ 1 + 2 ^ 4 = 18 She can buy items 2 and 4 for a cost of 64 and obtain a profit of 2 ^ 2 + 2 ^ 4 = 20 Out of all the possible combinations, the maximum profit obtained is by buying items 2 and 4 for a cost of 64 to obtain a profit of 20.