Let S be a set of intervals of integers and f(S) be the number of integers x for which there exist an interval T with T∈S and x,x+1∈T. In particular we have that f({[l,r]})=r−l.
Given an integer array A of length 2N. Consider a sequence of intervals [l1,r1],[l2,r2],…,[lN,rN] valid if r1<r2<⋯<rN, li<ri and (l1,r1,l2,r2,…,lN,rN) is a permutation of A.
Find the sum f({[l1,r1]}∪{[l2,r2]}∪⋯∪{[lN,rN]}) modulo 109+7 over all possible sequences of intervals.
Input
The first line contains one integer - N(1≤N≤105).
The next line contains 2N integers - A1,A2,…,A2N (1≤A1<A2<⋯<A2N≤109).
Output
Output the answer modulo 109+7.
The valid intervals are {([1,2],[3,4]),([1,3],[2,4]),([2,3],[1,4])} contributing with 2,3,3 respectively to the answer.