Special Technology

Time limit1sMemory limit1024 MB

Summary

Given student heights, find the greatest final height reachable when each student is hit at most once, printed modulo 10^9+7.

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

Problem

NLCS has the best technology in the world.

NLCS Jeju, whose technology is outstanding, developed a growth tool called "magic hammer" for students who want to grow taller.

NLCS Jeju ran an experiment that used the magic hammer on $N$ students who joined its clinical trial of the tool. When the hammer is used on a student, every other student grows taller by that student's height. The hammer is still a prototype, so each student can be hit at most once.

To show how powerful the magic hammer is, NLCS Jeju wants to make the tallest student as tall as possible after using the hammer. Find the greatest height that can be reached by using the hammer on the $N$ students.

Input

The first line contains the number of students $N$ .

The second line contains the height $H_i$ of each student, separated by spaces.

Output

Print the greatest height of a student that can be obtained by using the magic hammer appropriately. Heights can become very large, so print the remainder when the answer is divided by $10^9+7$ .

Constraints

$1 \le N \le 200\,000$
$1 \le H_i \le 10^9$

Examples1

Example 1
Input
```
2
2 10
```
Expected output
```
22
```