Problem Statement  
There are N cats sitting around a circle.
The cats are numbered 0 through N1 in clockwise order.
Note that as they sit around a circle, cat N1 is adjacent to cat 0.
The cats are playing a game and the winner will get a prize!
The game looks as follows:
 There is a single ball. Initially, cat 0 holds the ball.
 In each round of the game, the cat who currently holds a ball flips a biased coin. The coin will come up heads with probability p/1,000,000,000 and tails with probability 1(p/1,000,000,000).
 If the coin came up heads, the current cat will hand the ball to the next cat clockwise, otherwise the current cat will hand the ball to the next cat counterclockwise. Formally, if the current cat is cat j, heads means that the ball goes to cat (j+1) mod N and tails means that it goes to cat (j1) mod N.
 The game is played until each cat held the ball at least once. The cat who holds the ball at the end of the game is the winner.
In other words, the winner is the last cat to touch the ball.
Note that cat 0 holds the ball at the beginning, and this does count as holding the ball.
Hence, if there is more than one cat, cat 0 can never win the game.
Cat K wonders what is the probability that she will win the prize.
You are given the ints N, K, and p.
Return the probability that cat K wins.
  Definition   Class:  CatsOnTheCircle  Method:  getProb  Parameters:  int, int, int  Returns:  double  Method signature:  double getProb(int N, int K, int p)  (be sure your method is public) 
    Notes    Your return value must have an absolute or relative error smaller than or equal to 1e6   Constraints    N will be between 3 and 1,000,000,000, inclusive.    K will be between 1 and N1, inclusive.    p will be between 1 and 999,999,999, inclusive.   Examples  0)     Returns: 0.6999999999999985  This game has N=3 cats, labeled 0, 1, 2.
We have p=30,000,000, hence the coin will come up heads with probability 30,000,000/1,000,000,000 = 0.3 and tails with probability 0.7.
The game can look as follows:
 Cat 0 is given the ball.
 Cat 0 flips the coin. The coin comes up tails.
 Cat 0 hands the ball to cat (01) mod 3 = cat 2.
 Cat 2 flips the coin. The comes up tails again.
 Cat 2 hands the ball to cat (21) mod 3 = cat 1.
 At this moment, each cat has held the ball. The game ends and cat 1 gets the prize.
This particular sequence of events has probability 0.7*0.7 of occuring.
It can be shown that the probability that cat 1 wins the game is 0.7. 

 1)     Returns: 0.2  The coin that is flipped will come up heads with probability 1/2, and tails with probability 1/2. 

 2)     3)     Returns: 0.00391389439551009  
 4)    999999999  999999996  777777777 
 Returns: 0.05830903870125612  
 5)     Returns: 0.044981259448371  
 6)    534428790  459947197  500000000 
 Returns: 1.871156682766205E9  

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.
