Our hero - Maga is going to make a new contest for making the best teams. He is really excited about it. There will be S students in the contest. First N students in the final standings will be awarded.
He has a list( favourite students list ) what contains the best students in informatics Olympiad. His favorite students list contains M students. Though he is excited about the contest, he will enjoy it only if at least K of students from his favourite students list are awarded. He is wondering what are the chances of that happening. He needs your help. Tell him the probability that he will enjoy. It is known that each student has equal chance of being awarded.
Input: First line of input contains a single integer T, the number of test cases. In the next T lines, you are given 4 separated integers, S, N, M and K.
Output: For each test case, output the required probability with 6 digits after floating point.
Constraints: 1 <= T <= 100 1 <= S <= 1000 1 <= N <= S 1 <= M <= S 0 <= K <= M
Sample Input 3 10 10 5 3 10 4 6 4 3 2 2 1 Sample Output 1.000000 0.071429 1.000000
//I faced this question a few days back in a quiz, I am yet to understand how to proceed.
We need to use the hypergeometric distribution, where the probability is given by: \begin{align*} \mathbb{P}\left(\text{Our Maga enjoys!}\right) &= \frac{\displaystyle \sum_{i=0}^{\mathrm{M}-\mathrm{K}} \binom{\mathrm{S}-\mathrm{N}}{i}\, \binom{\mathrm{N}}{\mathrm{M}-i}}{\displaystyle \sum_{i=0}^{\mathrm{S}-\mathrm{N}} \binom{\mathrm{S}-\mathrm{N}}{i}\, \binom{\mathrm{N}}{\mathrm{M}-i}} \end{align*}