Mr M has recently learned about heaps from geeks for geeks. He started solving problems based on heaps.
However he got stuck on following problem. The problem is as follows:
How many distinct Max Heaps can be made from array of n integers which satisfies the following constraints :
- There are exactly
(n-1)distinct elements in the array. Or in other words there is exactly one element in the array which is repeated two times. - The only element which is repeated exactly two times is either the maximum element or the minimum element.
Note: In case of n=2 there will be only 1 distinct element . eg 2 2 .
As answer can be very large output it modulo 109+7.
Please help Mr M solve this problem on Heap. So that he can go ahead can learn new topics.
Input Format
- First line contains the number of test cases t. (t<=50)
- First line of every test case contains the number n (n<=1000)
- Second line of every test case contains n space separated integers (arr[i] <= 106)
Output Format
- For every test case output a single line containing the desired answer.
Note : Max Heap property is defined as the children nodes must have values less than or equals to the value of their parent.
Test Cases:
- 40 % of the marks contains n<=22
- 60 % of the marks contains n<=1000
Setter : Aayush Kapadia
(1) For first testcase n=3 and the repeated element is the minimum element. So only 1 max heap will be possible which is as follows
- 2 on the root. 1 as the left child of root and 1 as the right child of the root.
(2) For second testcase n=3 and the repeated element is the maximum element. So there will be 2 max heaps possible.
- 5 on the root. 5 as the left child of root and 1 as the right child of the root.
- 5 on the root. 1 as the left child of the root and 5 as the right child of the root.
