C. Beautiful Tables
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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 109 + 7.

Input

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

Output

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

Examples
Input
2
Output
2
Input
3
Output
81