Problem Link:
<a href = "https://www.codechef.com/NOV18B/problems/GMEDIAN"> Contest </a>
<b>Author</b>: <a href="https://www.codechef.com/users/teja349">teja349</a>
<b>Editorialist</b>: <a href="https://www.codechef.com/users/srvptk">srvptk</a>
Difficulty: Easy
Prerequisites: Maths, Observation, Precomputation
Problem:
For a sequence A[1],A[2],A[3],…,A[N]. Find the number of good subsequences. A subsequence is good if for a subsequence
A[i1],A[i2],A[i3],…,A[ik] (k>0, 1 <= i1 < i2 < i3 <…< ik <= N ) has its median as an element of this subsequence.
Explanation:
First we have to sort our sequence.
We observe that:
 The median in a sequence will be formed with a single element if size of sequence if odd.
 The median in a sequence will be formed with two elements if size of sequence is even.

For one element (ele) or two elements (ele1 and ele2) will form a median in a sorted sequence if there are equal number of elements
on both sides of the element.
<b> {k elements}, ele, {k elements} </b> <b> {k elements}, ele1, ele2, {k elements} </b>
<b>{x elements}, med, {y elements} </b>
Number of total subsequence having median <b>med</b> will be:
<ul>
<li>
total_subseq = 0
for i=0 to min(x,y){
total_subseq += x<b>C</b>i * y<b>C</b>i
}
</li>
</ul>
Observation:
For two elements to form a median which is in the sorted sequence, the two elements must be equal.(ele1 = ele2)
Optimization:
If we perform the computation of :
total_subseq = 0
for i=0 to min(x,y){ total_subseq += x<b>C</b>i * y<b>C</b>i } </li> </ul>
for every element, then it will exceed the time limit. So, we have to compute it earlier in the start.
How to do that?
Make an array Comp[1000][1000] where:

Comp[i][j] = 0
for k=0 to min(i,j){ Comp[i][j] += i<b>C</b>k * j<b>C</b>k } </li> </ul>
Also compute the value of Combination nCr in the start for all values of n and r ranging from 1 to 1000.
Complexity:
The maximum complexity will be for the computation of Comp array.It can be said to be O(N^3) but by adding a constraint, we can compute it in the required time.
The constraint is:
For every pair i and j, the value of Comp[i][j] will be computed only if:
(i+j) <= 1000
as they are a part of sequence whose maximum size can not be greater than 1000.
Don’t forget to compute the result modulo (10^9+7) since the number may be large.
Implementation

Comp[i][j] = 0