All Latin Squares

A square arrangement of numbers

1  2  3  4  5
2  1  4  5  3
3  4  5  1  2
4  5  2  3  1
5  3  1  2  4

is a 5 x 5 Latin Square because each whole number from 1 to 5 appears once and only once in each row and column.

Write a program that will compute the number of NxN Latin Squares whose first row is:

1 2 3 4 5.......N

Your program should work for any N from 2 to 7.

PROGRAM NAME: latin

INPUT FORMAT

• One line containing the integer N.

SAMPLE INPUT (file latin.in)

5

OUTPUT FORMAT

• A single integer telling the number of latin squares whose first row is 1 2 3 . . . N.

SAMPLE OUTPUT (file latin.out)

1344