- Practice
- Mathematics
- Algebra
- Shashank and List

# Shashank and List

# Shashank and List

Shashank is a newbie to mathematics, and he is very excited after knowing that a given l of cardinality *N* has (*2 ^{N} - 1*) non-empty sublist. He writes down all the non-empty sublists for a given set

*A*. For each sublist, he calculates sublist_sum, which is the sum of elements and denotes them by S

_{1}, S

_{2}, S

_{3}, ... , S

_{(2N-1)}.

He then defines a special_sum, *P*.

P = 2^{S1 } + 2^{S2 } + 2^{S3 } .... + 2^{S(2N-1) }and reports P % (10^{9} + 7).

**Input Format**

The first line contains an integer *N*, i.e., the size of list *A*.

The next line will contain *N* integers, each representing an element of list *A*.

**Output Format**

Print special_sum, P *modulo (10 ^{9} + 7)*.

**Constraints**

1 ≤ *N* ≤ 10^{5}

0 ≤ *a _{i}* ≤ 10

^{10}, where

*i ∈ [1 .. N]*

**Sample Input**

```
3
1 1 2
```

**Sample Output**

```
44
```

**Explanation**

For given list, sublist and calculations are given below

1. {1} and 2^{1} = 2

2. {1} and 2^{1} = 2

3. {2} and 2^{2} = 4

4. {1,1} and 2^{2} = 4

5. {1,2} and 2^{3} = 8

6. {1,2} and 2^{3} = 8

7. {1,1,2} and 2^{4} = 16

So total sum will be 44.