ACM Regional Programming Contest 1997

Problem No. 1 - Coin Flips

File name: coin.cc

Problem Description

Imagine tossing a coin n times. The probablility that the coin lands "heads" all n times is much less, say, than the probability that the coin lands "heads" for half of the tosses and "tails" for half of the tosses. In this problem, you are to compute the probability that a sequence of n coin flips results in a particular number of heads. To make matters more interesting, the coins being flipped are not necessarily "fair," in the sense that they need not have the same probability of landing "heads" as "tails."

Input

The input file will contain a number of lines of input: in each there will first be an integer N representing the number of times a coin is to be tossed. The second integer H is the number of heads you would like to have appear within those coin tosses. The third number in each line is a floating-point value between 0.0 and 1.0 (inclusive) that indicates the chances that a coin lands heads on any particular toss. The number of coin tosses will be between 1 and 1,000,000.

Output

For each input line, your program should print lines of the following format: 
  probability = x.xxxE-y
where each x is a decimal digit (the first is nonzero) and each y is a decimal integer with no leading zeroes or spaces. The number 
  x.xxxE-y
should represent in scientific notation (x.xxx * 10^-y) the probability that a sequence of N coin tosses results in exactly H heads with a coin biased according to the specified probability of landing heads. The output exponent y will always fit into a signed integer.

Example Input

1 1 0.25
2 0 0.1
8271 8271 0.5

Example Output

probability = 2.500E-1
probability = 8.100E-1
probability = 1.517E-2490