Our thanks to Clive Fraser for creating this task!
Ann and Bob like inventing new games. Among their collection of games they have two sets of outdoor skittles. The skittles are wooden cylinders, each about 1 metre tall. They are designed to be knocked over when struck by a ball. They are easily picked up and carried to a new location. Ann and Bob have a small square patio. It is 4 metres by 4 metres and is made up from 16 1-metre square paving slabs. Ann and Bob decide to design a game which begins with a skittle placed in the centre of each of the 16 paving slabs.
After some discussion, they came up with the following rules for the game. One player will set up the game and the other player will get the first move. The player who sets up the game places a numeric tag on each of the skittles to represent the score when that skittle is taken during the game. All of these numbers are distinct positive integers. The player setting up the game then takes a number of red tags and places these on any chosen skittles, provided that the number of red-tagged skittles is at least 2 and not more than 7.
The player making the first move can select any of the red-tagged skittles. If the number of red-tagged skittles is odd the first player scores the number on the chosen skittle. If the number of red-tagged skittles is even, the first player does not score anything for this skittle. (This ensures that both players will score from the same number of skittles as the game progresses) The first player then removes the chosen skittle and stands in its square. At this stage, all remaining red-tagged skittles are removed from the playing area and take no further part in the game. The game progresses with players alternating, making a valid move to remove a skittle and scoring the number on that skittle. The game finishes when there are no skittles remaining in the playing area. At this stage both players will have scored points from the same number of skittles. The player with the higher number of points wins.
The rules for a valid move are as follows. The next player begins by moving to the square currently occupied by the previous player, who moves off the playing area. The current player can select any skittle which is in a line of sight from the current position. In this context a line of sight is a straight line from the centre of the player's square to the centre of the square containing the chosen skittle, such that the line between the two does not pass through the central point of any other square which is occupied by a skittle. The following example should make this clear.
------ ------ ------ ------
| | | | |
| 1 | 2 | 3 | 4 |
| | | | |
------ ------ ------ ------
| | | | |
| 5 | 6 | 7 | 8 |
| | | | |
------ ------ ------ ------
| | | | |
| 9 | 10 | 11 | 12 |
| | | | |
------ ------ ------ ------
| | | | |
| 13 | 14 | 15 | 16 |
| | | | |
------ ------ ------ ------
The diagram above shows how the 16 skittles are placed on the playing area. The numbers are used simply to identify the different skittles. These are not to be confused with the score tags. Consider a game where the setter Ann decides to put red tags on 7 of the skittles. The skittles tagged by Ann are numbered 1, 6, 10, 11, 13, 14 and 16. Bob can now choose any of these 7 skittles for his first move. Bob chooses skittle number 1. Because the number of red-tagged skittles is odd, Bob scores the value on the score tag for this skittle. (We are not concerned with the score at this stage) Bob removes skittle number 1 and Ann removes all of the remaining red-tagged skittles from the board. This concludes the first move. It is now Ann to move, so she changes places with Bob and is standing on square 1. The following diagram shows the current state of the playing area. Ann is at the position marked A.
------ ------ ------ ------
| | | | |
| A | 2 | 3 | 4 |
| | | | |
------ ------ ------ ------
| | | | |
| 5 | | 7 | 8 |
| | | | |
------ ------ ------ ------
| | | | |
| 9 | | | 12 |
| | | | |
------ ------ ------ ------
| | | | |
| | | 15 | |
| | | | |
------ ------ ------ ------
Ann can choose to remove any skittle which is in a line of sight from her current position. The possible choices are 2, 5, 7, 8, 12 and 15. Note that skittles 3 and 4 are unavailable because they are blocked by skittle 2 which lies on the line of sight. Similarly skittle 9 is blocked by skittle 5. If Ann chooses skittle 5 she will score the value of its score tag and then remove it from the game. Bob will then take Ann's place (at the skittle 5 square) ready for his move.
So the first two skittles removed are 1 and 5. Suppose that the skittles removed (in order) for this game are 1, 5, 15, 4, 8, 9, 2, 7, 3 and 12. We will call this the move sequence for the game. Note that removing skittle 15 at Bob's second move is only possible because skittle 10 is no longer on the playing area.
Ann and Bob were wondering about suitable strategies for playing the game. However, they soon realised that the number of possible move sequences can be very large. They decided to concentrate on this first. They calculated, for the current game, that there are 1198080 different valid move sequences. Note that a move sequence starts with one of the red-tagged skittles. None of the other red-tagged skittles can be used later in the move sequence. So for this game any of the 7 red-tagged skittles can start the move sequence. The remainder of the sequence is then made up of valid moves within the remaining (non red-tagged) skittles.
In this problem you will be given several game setup positions and are asked to calculate the number of different move sequences which could arise from the given setup.
Input/Output description: The first line of the input data will contain a single integer N, the number of game setup positions. N lines will follow. Each of these will contain a sequence of between 2 and 7 space-separated integers. These are the skittles which have been given a red tag. Find the number of possible move sequences which can be achieved by following the rules. Combine your answers into a single string, separated by spaces.
Example:
input:
3
1 6 10 11 13 14 16
2 6 8 13 15 16
3 5 6 9 12
answer:
1198080 7291154 42833724