Problem Statement   In a traditional lottery, the players are trying to guess a set of K numbers that is selected at random.
The K numbers are distinct and each of them is between 0 and N1, inclusive.
Usually, the chances of winning in such a lottery are very small.
However, it has come to your attention that your local lottery may be biased.
You now want to analyze this bias.
Your source has sent you pseudocode of the algorithm used by your local lottery.
The pseudocode is shown below.
The values returned by the function random() are mutually independent.
def random(P):
generate and return a random value between 0 and N1, inclusive,
in such a way that the probability of returning value i is P[i] / 1000
def lottery(K,P):
selected_numbers = an empty set
while selected_numbers has fewer than K elements:
candidate = random(P)
if candidate is not in selected_numbers:
add candidate to selected_numbers
return selected_numbers
You are given the int K and the int[] P: the probability distribution used in the pseudocode.
Your favorite number is the number 0.
You would like to compute the probability that this number will be among the K selected numbers.
This probability can be expressed as an irreducible fraction Q / R.
It can be shown that under the constraints of this problem there exists exactly one integer Y between 0 and 10^9+6, inclusive, that satisfies the modular equation R * Y = Q (mod 10^9+7).
Return the value of Y.   Definition   Class:  RiggedLottery  Method:  getProbability  Parameters:  int, int[]  Returns:  int  Method signature:  int getProbability(int K, int[] P)  (be sure your method is public) 
    Constraints    N will be between 1 and 50, inclusive.    K will be between 1 and N, inclusive.    P will contain exactly N elements.    Each element in P will be between 1 and 1000, inclusive.    The sum of all elements of P will be 1000.   Examples  0)     Returns: 100000001  In this lottery we are selecting one number from the set {0,1,2}.
The number 0 is selected with the probability 300/1000.
The corresponding irreducible fraction is 3/10.
The correct return value is 100000001 because 10 * 100000001 = 3 (mod 10^9+7). 

 1)     Returns: 350000003  The probability that 0 is the first number added to selected_numbers is obviously 0.2.
It can be computed that the probability that 0 is the second number added to selected_numbers is 0.35.
As these two options are mutually exclusive, the total probability that 0 is selected is 0.55 = 11/20.
We have 20 * 350000003 = 11 (mod 10^9+7). 

 2)     3)     4)    24  {13,8,49,2,12,69,30,22,21,48,18,8,37,30,13,10,12,30,15,63,33,38,46,10,93,52,26,11,13,14,19,48,1,9,5,31,7,4,10,20} 
 Returns: 959464924  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
