Given N bags, each bag contains Bi chocolates. There is a kid and a magician. In one unit of time, kid chooses a random bag i, eats Bi chocolates, then the magician fills the ith bag with floor(Bi/2) chocolates.

Find the maximum number of chocolates that kid can eat in A units of time.

NOTE:

floor() function returns the largest integer less than or equal to a given number.

Return your answer modulo 10^9+7

Input Format

First argument is an integer A.

Second argument is an integer array B of size N.

Output Format

Return an integer denoting the maximum number of chocolates that kid can eat in A units of time.

Example Input

Input 1:

A = 3

B = [6, 5]

Input 2:

A = 5

b = [2, 4, 6, 8, 10]

Example Output

Output 1:

14

Output 2:

33

Please note that python code for above question should pass large test cases, and all corner test cases, reasoning for below MCQs is also needed, please dont copy (unhelpful if copied or didn't answer all)

1. What will be the output of the following Python code?

s=set()

type(s)

a) <'set'>

b)

c) set

d) class set

2. The following Python code results in an error.

s={2, 3, 4, [5, 6]}

a) True

b) False

3. Set makes use of ______

Dictionary makes use of ________

a) keys, keys

b) key values, keys

c) keys, key values

d) key values, key values

4. Which of the following lines of code will result in an error?

a) s={abs}

b) s={4, 'abc', (1,2)}

c) s={2, 2.2, 3, 'xyz'}

d) s={san}

5. What will be the output of the following Python code?

s={2, 5, 6, 6, 7}

s

a) {2, 5, 7}

b) {2, 5, 6, 7}

c) {2, 5, 6, 6, 7}

d) Error

6. Input order is preserved in sets.

a) True

b) False

7. Write a list comprehension for number and its cube for:

l=[1, 2, 3, 4, 5, 6, 7, 8, 9]

a) [x**3 for x in l]

b) [x^3 for x in l]

c) [x**3 in l]

d) [x^3 in l]

8. What will be the output of the following Python code?

s={1, 2, 3}

s.update(4)

s

a) {1, 2, 3, 4}

b) {1, 2, 4, 3}

c) {4, 1, 2, 3}

d) Error

9. Which of the following functions cannot be used on heterogeneous sets?

a) pop

b) remove

c) update

d) sum

10. What will be the output of the following Python code?

s=set()

type(s)

a) <'set'>

b)

c) set

d) class set