Ecology

Ecology has several ways to estimate how many animals live in an area. This problem surveys birds with the method below.

The survey runs for D days. Before it starts, no bird carries a tracker. On each day of the survey you catch C birds. Every caught bird without a tracker gets one, and a bird that already carries a tracker is left alone. At the end of the day you release all of the caught birds.

Which birds you catch is completely random. Every C-element subset of the N birds in the area is equally likely, and the days are independent of each other. If C is larger than N, you catch all N birds in the area that day.

The area holds N birds. Write a program that computes the probability that exactly M birds carry a tracker once the survey ends.

The first line contains N, C, D and M, separated by single spaces. (1 ≤ N ≤ 20, 1 ≤ C ≤ 20, 1 ≤ D ≤ 5, 0 ≤ M ≤ N)

Print on the first line the probability that exactly M birds carry a tracker once the survey ends. Round it to ten digits after the decimal point and pad with zeros when the digits run out. A probability of 1 prints as 1.0000000000 and a probability of 0 prints as 0.0000000000.

Take N = 3, C = 1, D = 2. After the first day one bird carries a tracker. On the second day you catch that same bird with probability 1/3, and you catch a bird without a tracker with probability 2/3. The probability that two birds carry a tracker is therefore 2/3.