Given an integer and integers , you should divide these numbers into groups and each group contains exactly two integers. Now define the weight of a group as the difference between the two integers in the group, and the weight of a dividing manner as the variance of the group weights. Determine the expectation value of the dividing manner weight modulo .

Here, the variance of numbers equals , where .

The first line contains one integer .

The second line contains  integers .

Only one line containing one integer, denoting the answer.

2
2 2 3 4

748683265

There are 3 dividing manners:

* , the weights are  respectively, and the variance is 

* , the weights are  respectively, and the variance is 

* , the weights are  respectively, and the variance is 

where  denotes the first 2 while  denotes the second  in sample input.

Hence, the answer is .