jordon goes to shop to buy n shoes. After his purchase, the shopkeeper offers him a crazy refund on his bill.

the shopkeeper tells jordan that he can select any of floor(n/2) shoes and the shopkeeper will refund the sum of the square of the prices of those shoes.

Now, before buying the shoes, jordon can perform an infinite number of the following operations:
-> select any pair of shoes
-> let's say their cost is A and B
-> update the cost of the first shoe (A or B)
-> update the cost of the first shoe (A and B)

Now, jordan wonders what is the maximum refund he can get if the number and cost of the shoes are already decided.
Help jordan get the maximum benefit of this craziness.

Since the answer may be too large, output the answer modulo 1e9 + 7

constraints:
1 <= N <= 10^5
1 <= Arr[i] <= 10^9