Read problems statements in Mandarin Chinese and Russian.
Sereja have an array that consist of n integers a[1], a[2], ..., a[n]. Now Sereja want to delete some(possible none, but not all) elements from the array, such that arithmetical mean of all remaining numbers will as big as possible.
Help Sereja, find number of ways to delete numbers.

------ Input ------

First line contain integer T - number of testcases. T tests follow. First line of each testcase contain integer n. Next line contain n integers a[1], a[2], ..., a[n].

------ Output ------

For each testcase print the answer modulo 10^{9}+7.

------ Constraints ------

1 ≤ T ≤ 10
1 ≤ n ≤ 10^{5}
1 ≤ a[i] ≤ 10^{5}

------ Note ------

Test #0-1(25 points) n ≤ 20
Test #2(25 points) n ≤ 1000
Test #3-4(50 points) n ≤ 100000

----- Sample Input 1 ------
2
1
1
4
1 2 1 2
----- Sample Output 1 ------
1
3

见题面

见题面