Disastrous Doubling

Time limit2sMemory limit512 MB

Summary

Each hour the bacteria double, then an experiment consumes b_i; report the remainder modulo 1e9+7 or error if supply runs short.

Level: Medium6 of 10
Topics: Simulation, Math, Greedy, Implementation
Solved: No attempts yet

Problem

A scientist, E. Collie, is starting a series of experiments with bacteria. She has one bacterium right now. This species doubles in number every hour, so one hour later there are 2 bacteria.

E. Collie runs one experiment every hour for $n$ consecutive hours. She starts the first experiment exactly one hour after the first bacterium starts growing. Experiment $i$ needs $b_i$ bacteria. In other words, every hour the colony doubles first, and then that hour's experiment takes the bacteria it needs.

How many bacteria are left directly after the last experiment starts? If at any point there are not enough bacteria for an experiment, print error instead.

The answer can be very large, so print it modulo $10^9 + 7$ .

Input

The input consists of two lines.

The first line contains an integer $n$ , the number of experiments. ( $1 \le n \le 10^5$ )
The second line contains $n$ integers $b_1, \ldots, b_n$ separated by spaces, where $b_i$ is the number of bacteria used in the $i$ th experiment. ( $0 \le b_i \le 2^{60}$ )

Output

Print one line with the number of bacteria that remains after all experiments, taken modulo $10^9 + 7$ . If the bacteria ever run short, print the lowercase word error instead of a number.

Examples4

Example 1
Input
```
3
0 0 0
```
Expected output
```
8
```
Example 2
Input
```
5
1 1 1 1 1
```
Expected output
```
1
```
Example 3
Input
```
5
0 2 2 4 0
```
Expected output
```
0
```
Example 4
Input
```
5
0 2 2 4 1
```
Expected output
```
error
```