Monsters

Time limit1sMemory limit512 MB

Summary

Each monster with k fingers can form 2^k distinct sums by lifting any subset of powers of two; output the sum of 2^ki mod 1e9+7 over all monsters.

Level: Easy2 of 10
Topics: Math, Combinatorics, Implementation, Number theory
Solved: No attempts yet

Problem

The 2017 International Congress of Monsters gathers n monsters from all over the world. Their chairman must solve the following problem. The ith monster (1 ≤ i ≤ n) has ki fingers, indexed from 0 to ki - 1, and can lift j of those fingers (0 ≤ j ≤ ki) to obtain a number as follows: when a finger is lifted, 2 raised to that finger's index is added to the current number. As a result, the ith monster can count nri distinct numbers on his fingers. The value to compute is nr1 + nr2 + … + nrn, modulo 109+7.

Compute this sum modulo 109+7.

Input

The first line contains n.

The second line contains n positive integers k1, k2, …, kn, the number of fingers of each monster.

Output

Print a single positive integer, the requested sum modulo 109+7.

Constraints

n ≤ 200,000
0 ≤ ki ≤ 1,000,000,000
Fingers are indexed from 0.

Hint

The first monster can obtain 8 numbers:

0: no finger lifted
1: the lifted finger's index is 0
2: the lifted finger's index is 1
3: the lifted fingers' indexes are 0 and 1
4: the lifted finger's index is 2
5: the lifted fingers' indexes are 0 and 2
6: the lifted fingers' indexes are 1 and 2
7: the lifted fingers' indexes are 0, 1, and 2

The second monster can obtain 128 numbers.

Examples1

Example 1
Input
```
2
3 7
```
Expected output
```
136
```