Problem E

Donkey

Long ago, a number of farmers wanted to sell their donkeys. These farmers lived in a small village and the marketplace was in the capital. There was only one small road from the village the farmers lived in to the capital, and one day the farmers left for the long journey towards the capital. Every farmer wanted to travel as fast as possible to be the first to sell his donkey, but there was one major problem: the donkeys were very stubborn; everytime a donkey reached a river there was a chance that he would stay there for some time, not willing to cross the river. However, two donkeys never rested at the same river.

The game 'Donkey' is derived from this legend: N players (numbered from 1..N) start with their donkey in the village. Between the village and the capital are M rivers. The players take turns in throwing a fair, 6-sided die and move their donkey the thrown number of rivers towards the capital. Since only one donkey can rest at a river, the donkey is placed at the next free river if necessary. After player 1 has thrown the die, it is player 2's turn, etc. After N comes 1. The player that passes all rivers first wins the game.

This is an example of a 'Donkey' gameboard, where N = 2 and M = 6. Player 1's donkey is located at river 4 and player 2's donkey is located at river 1.

Your task is to give the probability that player 1 wins the game, given a certain board position.

Input Specification

The first line contains a single integer which equals the number of test cases that follow. Each of the following lines contains one test case. The first integer on a line gives the number of rivers M, the second integer gives the number of players N (1 <= N <= 4 and N × M <= 50). Then follow N integers P_i (0 <= P_i <= M, 1 <= i <= N), representing the position of the ith player. The river closest to the village has number 1, the river closest to the capital has number M. The village has number 0. Two donkeys may not be positioned at the same river. However, more than one donkey may be standing in the village. The last integer on the line gives the player, whose turn it is.

Output Specification

For every situation you have to print the following line, giving the game number (1 for the first, 2 for the second, ...) and the probability player 1 wins with an accuracy of 3 decimals:

Game N:the probability that player 1 wins = D.DDD

Example Input

3
3 2 1 2 1
6 3 1 2 3 2
6 3 4 1 3 2

Example Output

Game 1:the probability that player 1 wins = 0.667
Game 2:the probability that player 1 wins = 0.093
Game 3:the probability that player 1 wins = 0.366

This page maintained by Ed Karrels.
Last updated January 3, 1998