This problem was created by Clive Fraser - many thanks! You are strongly advised to have solved problem #319 Tower of Hanoi Rules before attempting this one.
The Towers of Hanoi problem is well known and well documented. There are 3 pegs, left, middle and right.
At the start of the puzzle, a tower of n disks is placed over the left peg.
The disks are placed in size order with the largest at the bottom.
The puzzle is to rebuild the tower over the right peg, using the minimum number of moves.
In any move we can take the topmost disc from any pile and place it onto either of the other piles,
provided that it is smaller than any discs that are already on that pile.
It is well known that the minimum number of moves required is 2^n - 1. Hence there are 2^n
different arrangements of the three towers (including the start and finish positions).
There is only one way of solving the puzzle in the minimum number of moves, so each arrangement of discs
which forms part of the solution occurs only once. However, if we ignore the disc composition of the towers
and consider only the heights of the towers, we now find that the same arrangement of heights can occur
multiple times during the course of the optimal solution. (Note that the height of a tower is just the number
of discs which it contains.) As an illustration, consider a puzzle with 4 discs. The optimum solution has 15
moves and there are 16 different disc arrangements making up the solution.
The following table shows the heights of the three towers at the end of each move
(move 0 represents the starting position).
move 0 [4, 0, 0]
move 1 [3, 1, 0]
move 2 [2, 1, 1]
move 3 [2, 0, 2]
move 4 [1, 1, 2]
move 5 [2, 1, 1]
move 6 [2, 2, 0]
move 7 [1, 3, 0]
move 8 [0, 3, 1]
move 9 [0, 2, 2]
move 10 [1, 1, 2]
move 11 [2, 1, 1]
move 12 [2, 0, 2]
move 13 [1, 1, 2]
move 14 [0, 1, 3]
move 15 [0, 0, 4]
Move 1 moves a disk from the left peg to the middle peg, move 2 moves a disc from the left peg to the right
peg, move 3 moves a disc from the middle peg to the right peg, and so on until we have all 4 discs on the
right peg after move 15. Notice that the height arrangements are not unique. For example, the height
arrangement [2, 1, 1] occurs 3 times; at moves 2, 5 and 11. This problem asks you to find the number
of times a given height arrangement occurs in the optimum solution for a puzzle with n discs.
Since this number can be quite large, you are asked to give the answer modulo 1000000007 (10^9 +7).
The number of discs in any problem is guaranteed to be less than 600. In the example given below, for a
puzzle with 7 discs, the height arrangement [3, 2, 2] occurs 14 times within the optimal solution.
Input/Output description: The first line of the input data will contain a single integer N, the number
of puzzles to solve.
N lines will follow. Each line contains 4 numbers. The first of these is the number of discs in the puzzle.
The remaining 3 numbers are the heights of the left, middle and right towers respectively.
(Note that the sum of the three tower heights is the same as the number of discs). For each of these sets of
data you must find the number of times the tower height arrangement appears in the optimum solution for the
given number of discs. Give all answers (modulo 1000000007) on a single line, separated by single spaces.
Example:
input:
7
7 3 2 2
15 5 6 4
32 12 9 11
58 20 24 14
128 42 37 49
205 75 73 57
384 142 139 103
answer:
14 1530 96171790 831693973 887270096 226662566 64110636
Author's note: Although the problem requires some careful thought, it can be solved using only simple routines and simple arithmetic. There is no need to use or to derive any formulae. In fact the checker software uses only these simple routines and finds all of the required answers in a total time of less than one second (in normal Python). Those who have the necessary skills are encouraged to look for a combinatoric solution but this really isn't necessary.