21360_Rooks

Many mathematical problems on chessboard have been studied. The 8-queens problem, may be the most famous, is to place 8 queens on the chessboard so that they do not attack each other. This problem is probably as old as the chess game itself, and thus its origin is not known, but it is known that Gauss studied this problem.

The same sort of question about rooks can be asked. Two rooks are said to be attacking each other if they are placed in the same row or column of the chessboard. How many ways are there to place 8 non-attacking rooks on a chessboard? The answer is quit easy, and can be soled generally: on an n by n chessboard, the number of ways to place n non-attacking rooks is n! (The two ways of placing on 2-by-2 chessboard are shown in Figure 1.

Figure 1   two ways of placing on 2-by-2 chessboard

Since a n-by-n chessboard can also be considered to be a n+1 by n+1 grid, a path can be drawn along the grid line from the upper left comer to the lower right comer by going right or down at each turning.

A configuration of a chessboard is a placing of rooks with a path that all rooks are below the path (all three configurations of 2-by-2 chessboard are shown in Figure 2).

Figure 2   all configurations of 2-by-2 chessboard

Your task is to write a program to calculate the number of configurations in n-by-n chessboard.

The input is a sequence of positive integers each in a separate line. The integers are between 1 and 100, inclusive, indicating the size of the chessboard. The end of the input is indicated by a zero.

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of configurations of the chessboard with the input size. No other characters should be inserted in the output.

2
0

3