Problem description
Clarissa Adele Fray (a.k.a Clary) has found out that she is a shadowhunter, a human with angelic qualities. She can create her own runes (magical spells). Last week, she created many powerful runes.
Right now, she is facing several underworld demons, help her find the number of ways, such that the arithmetic mean of the selected runes is max.

Input
First line contains number of test cases.For each test case,there are 2 lines-First line : the number of runes Clary created in the last week.Second line : power of each rune, separated by space

Output
For each test case, print the number of ways (modulo 10^9+7), such that the arithmetic mean of the selected runes in max, in new line.

Constraints
SubTask 1 - 70 Points

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ Power of Rune ≤ 10^5

SubTask 2 - 30 Points

1 ≤ T ≤ 2
1 ≤ N ≤ 10^3
1 ≤ Power of Rune ≤ 100

Example
Input:
2
1
100
3
80 90 90

Output:
1
3

Explanation
Test Case 1 : There is only one way:
She can select 100
Test Case 2 : There are 3 ways:
She can select 90 (at 2nd position)
She can select 90 (at 3rd position)
She can select 90,90 (both 2nd and 3rd position)

见题面

见题面