Drawing Pebbles

Given pebble counts per color, compute the probability that K randomly drawn distinct pebbles all share one color, printed to 10 decimals.

Medium4CombinatoricsMathProbabilityImplementationInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

A secret box holds NN pebbles. Each pebble has one of the colors numbered 11 through MM.

You draw KK pebbles at random from the box. Write a program that computes the probability that every drawn pebble has the same color. Every choice of KK distinct pebbles is equally likely.

Input

The first line contains the number of colors MM (1M501 \le M \le 50).

The second line contains MM integers, the pebble count of color 11 through color MM in that order. Each value is at least 11 and at most 5050. The total number of pebbles NN is the sum of these MM values.

The third line contains KK (1KN1 \le K \le N).

Output

Print the probability that every drawn pebble has the same color, rounded half up at the 11th digit after the decimal point and shown to the 10th digit. Always print exactly 10 digits after the decimal point. A probability of 11 is printed as 1.0000000000.