F. Twin Trucks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lazy Bob has recently discovered how cool trucks are, so one day he decides to stand on the side of the freeway and stare at some. In one given day, he knows that he will see $$$N$$$ ($$$2 ≤ N ≤ 200,000$$$) trucks pass by him.

He notices that each truck has a defining feature: the length between the front and back wheels, given by an integer $$$a_i$$$ ($$$1 ≤ a_i ≤ 1,000,000$$$). All of the trucks he sees have different $$$a_i$$$ values.

Now, Bob wants to take two pictures, each containing a different truck, to show to his friends at school. Because longer trucks are cooler, but he wants to show his friends the variety of lengths in trucks, he assigns a pair of trucks with lengths $$$a_i$$$ and $$$a_j$$$ an arbitrary score of $$$(a_i + a_j)^{|a_i - a_j|}$$$. Please help Bob find the maximum such value for any pair of trucks $$$i ≠ j$$$. Because this value can be very large, give Bob the maximum truck-pair score (mod $$$10^9 + 7$$$). Just to clarify, Bob wants [the maximum truck-pair score] (mod $$$10^9 + 7$$$), not the maximum remainder of a truck-pair score when divided by $$$10^9 + 7$$$.

Input

Line 1: One integer $$$N$$$ ($$$2 ≤ N ≤ 200,000$$$).

Line 2: $$$N$$$ space-separated integers: $$$a_1$$$, $$$a_2$$$, … $$$a_N$$$ ( $$$1 ≤ a_i ≤ 1,000,000$$$, all $$$a_i$$$ distinct), each describing the $$$i$$$th truck's length.

Output

Line 1: One integer representing the remainder when the maximum truck-pair score between any pair of trucks is divided by $$$10^9 + 7$$$.

Example
Input
3
1 5 2
Output
1296
Note

Here are the scores for each pair of trucks:

$$$1$$$ & $$$2$$$: $$$(1+5)^{|1-5|} = 6^4 = 1296$$$

$$$1$$$ & $$$3$$$: $$$(1+2)^{|1-2|} = 3^1 = 3$$$

$$$2$$$ & $$$1$$$: $$$(5+1)^{|5-1|} = 6^4 = 1296$$$

$$$2$$$ & $$$3$$$: $$$(5+2)^{|5-2|} = 7^3 = 343$$$

$$$3$$$ & $$$1$$$: $$$(2+1)^{|2-1|} = 3^1 = 3$$$

$$$3$$$ & $$$2$$$: $$$(2+5)^{|2-5|} = 7^3 = 343$$$

The maximum truck-pair score is between trucks $$$1$$$ & $$$2$$$, and that value, when taken (mod $$$10^9 + 7$$$), is $$$1296$$$.