404997: GYM101733 C Beautiful Tables

Victor usually spends free time with reading books, solving riddles and puzzles.

Yesterday he decided to come up with his own puzzle. One should fill the table of size n × n with integers from 1 to n in a such way that the sum of the numbers in each row and the sum of numbers in each column is divisible by n. Each integer from 1 to n can be used arbitrary number of times.

Help Victor to determine the number of distinct tables satisfying the requirements of the puzzle. Two table are considered to be distinct if they differ in at least one cell. As the number Victor wants to compute may be pretty big, you only need to find its remainder modulo 10⁹ + 7.

The only input line contains a single integer n (1 ≤ n ≤ 1000), the number of row and the number of columns of the table.

Print the number of appropriate tables modulo 1 000 000 007.

2

2

3

81