Set Difference

Read problems statements in Mandarin Chinese and Russian.
Churu is working as a data scientist in Coderpur. He works on a lot of data on the daily basis. One day, he found an interesting problem, which was very easy to solve for small data but was getting more complex with increasing number of data points. So, Churu needs your help in solving this problem.
Given a set S of N nonnegative integers (Some integers might occur more than once in the set), find out the value of SETDIFF(S).
Where max(s) represents the maximum value in set s whereas min(s) represents the minimum value in the set s. As value of SETDIFF(S) can be very large, print it modulo (10^{9} + 7) .
There might be repeated values in the set. For set S = {1,2,2}, consider that first 2 is not same as the second 2 and there will be two different subsets {1,2}. See last sample case for the more clarifications.
Input
 First line of input contains an integer T denoting number of test cases.
 For each test case, first line will contain an integer N denoting number of elements in set S.
 Next line contains N space separated integers denoting the set S.
Output
For each test case, print a single integer representing the answer of that test case.Note
Two subsets will be called different if there exists an index i such that S[i] occurs in one of the subset and not in another.
Constraints
Subtask #1: 20 points
 1 ≤ T ≤ 5, 1 ≤ N ≤ 1000, 0 ≤ value in set ≤ 10^{9}
Subtask #2: 25 points
 1 ≤ T ≤ 5, 1 ≤ N ≤ 10^{5}, 0 ≤ value in set ≤ 1000
Subtask #3: 55 points
 1 ≤ T ≤ 5, 1 ≤ N ≤ 10^{5}, 0 ≤ value in set ≤ 10^{9}
Example
Input: 4 2 1 2 3 1 2 3 4 1 2 3 4 3 1 2 2 Output: 1 6 23 3
Explanation
For first case answer will be 21 = 1.
For the second case:
Subset = {1}, max(s)min(s) = 0.
Subset = {2}, max(s)min(s) = 0.
Subset = {3}, max(s)min(s) = 0.
Subset = {1,2}, max(s)min(s) = 1.
Subset = {2,3}, max(s)min(s) = 1.
Subset = {1,3}, max(s)min(s) = 2.
Subset = {1,2,3}, max(s)min(s) = 2.
So the output will be 1+1+2+2 = 6.
In the last case, there are three subsets, {1,2}, {1,2} and {1,2,2} having max(s)  min(s) = 1 for each.
Author:  amitpandeykgp 
Tags  amitpandeykgp, basicmath, easy, may15 
Date Added:  27022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions