WINGOLD - Win gold medal

In a game there are infinite number of levels. In order to go to the next level, a player has to clear all the preceding levels. A player cant go further, if he fails to clear the level. Each player has a probability p of clearing the level (which is independent of the other players and the level number). For example, if p =1/2 there is a probability 2^(-n-1) that a particular game will have exactly n levels cleared. A player will get Gold medal if he clears the maximum number of levels. If the maximum number of levels reached is common between two or more players, then no one wins the gold medal. What is the probability that a Gold medal is given to any player?

Input

T number of test cases each case follow
p n m . probability of clearing level for each player, number of player, number of levels in game

Output

T line each probability that gold medal is given round off to 4 significant digits

limit:

1<=T<10000
1<=n<1000
1<=m<100
0<=p<=1.0

Example

Input:
6
0.43 3 2
0.5 3 4
0.2 3 4
0.1 4 5
0.9 3 3
1.0 4 4
Output: 0.4490
0.6244
0.4184
0.3014
0.0275
0.0000

Added by:pankaj
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own, DOPE 2011

hide comments
2019-05-14 17:39:07
Second to @:D's post, the given m levels of the game and an infinite number of levels have different solutions.
Also this problem seems didn't consider the corner case of n==1.
2012-09-26 05:59:50 Gopal Rander
T*m*log n solution gives TLE..
2012-02-08 08:45:50 Walrus
The constraints m>=1 and n>=1 are not satisfied. Please correct the test data.
2011-02-21 12:34:23 :D
"In a game there are infinite number of levels." Please correct that since there is a FINITE number of those and it kinda makes a difference :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.