Problem
You are given a multiset �A containing �N integers.
Your task is to count the number of distinct subsets of the multiset �A, that have a unique mode. Since this number can be huge, print it modulo 10000000071000000007.
Note that if two subsets form the same set of values, they are not counted as different subsets. For example, consider �=[1,1,2,1]A=[1,1,2,1], the distinct subsets of the multiset are {1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}{1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}.
Input Format
- The first line of input will contain a single integer �T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer �N — the number of integers in the multiset.
- The next line contains �N space-separated integers, denoting the elements of the multiset.
Output Format
For each test case, output on a new line, the number of distinct subsets of the multiset �A, that have a unique mode, modulo 109+7109+7.
Constraints
- 1≤�≤2⋅1041≤T≤2⋅104
- 1≤�≤1051≤N≤105
- 1≤��≤1091≤Ai≤109
- The sum of �N over all test cases won’t exceed 2⋅1052⋅105.
Sample 1:
Input
Output
3 4 1 1 1 2 3 1 1 1 4 1 2 3 4
6 3 4
Explanation:
Test case 11: The distinct subsets of the multiset are: {1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}{1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}.
Subsets with unique mode are {1},{2},{1,1},{1,1,1},{1,1,2},{1,1,1,2}{1},{2},{1,1},{1,1,1},{1,1,2},{1,1,1,2}. Note that, in all these subsets, there is exactly one element having maximum frequency, and thus, there is a unique mode.
Test case 22: The distinct subsets of the multiset are: {1},{1,1},{1,1,1}{1},{1,1},{1,1,1}. Note that, all these subsets have unique mode.
Test case 33: The distinct subsets having unique mode are: {1},{2},{3},{4}{1},{2},{3},{4}. Some distinct subsets that do not have unique mode are {1,2},{2,3},{2,3,4},{1,3,4}{1,2},{2,3},{2,3,4},{1,3,4}.
