Game

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

There are N people playing a game. The rules of the game are described as follows:
Initially, there are N people numbered from 1-N. And they are arranged in a queue by the order from 1-N. Each round, only 4 people get into the game and each people has equally probability to win the game. The winner can continue to games, the loser will go to the end of the queue according to the order before this round (if someone was the winner before this round, we can consider he was the head of the queue).
The first round of game, the first four people start to play the game. If someone continuously wins the game M times, he will become the final winner.
Now I want to know the probability for the K-th people to become the final winner.

Input

The first line of input contains T, the number of test cases.
Flowing T line, each line contains 3 integer N, M, K.(4<=N<=10, M<=10,K<=N)

Output

Each output should occupy one line. Each line should start with "Case #i : ", followed by the answer round to six decimal places.

Sample Input

3 4 1 1 5 1 5 5 2 1

Sample Output

Case #1: 0.250000 Case #2: 0.000000 Case #3: 0.217626

Hint

zhoujiaqi2010

Source

2012 Multi-University Training Contest 3

提交代码