Famous photographer auo has an \(\mathbf{N}\) story pyramid-shaped house. They hung up some photographs in each room and auo's cat dero, being the biggest fan of auo, loves to wander around the house and look at the photos.

auo's house is built in the shape of a pyramid. The top-most floor has one room and every other floor has one more room than the one upstairs. In one trip, dero starts from the top floor and moves downwards, visiting one room on each floor. Since the house is pyramid-shaped, dero can move to the room that's directly below or the room at the right side of that room. So dero can only move to two rooms on the floor below (see the figure). Given the number of photographs in each room, can you find the maximum number of photos dero can see in one trip?

Input

In the first line, you will be given the number of stories \(\mathbf{N}\). In the following \(\mathbf{N}\) lines, there will be the number of photographs \(\mathbf{P_i}\) in each room on a floor, from top to bottom.

• \(2 \leq \mathbf{N} \leq 1000\)

• \(1 \leq \mathbf{P_i} \leq 10^9\)

Output

In a single line, print the maximum possible number of photos modulo \(10^9+7\).

Examples

Input 1:

4
1
4 8
3 9 5
2 4 7 9

Output 1:

25

Explanation

Starting from the 4th floor, dero moves to rooms with 8, 9, 7 photos respectively. So the answer is 1+8+9+7 = 25. Remember, since the house is a pyramid, it is only possible to move from one room to two rooms in the lower floor.