Zigzag Lineup

There are N students with distinct heights. Number 1 is the shortest student and number N is the tallest student. Arrange all students in one line, using each student exactly once.

Any student may stand in the first position, and any remaining student may stand in the second position. From the third position onward, the next student's height is determined by comparing the previous two students.

• If the immediately previous student is taller than the student before them, the next student must be shorter than the immediately previous student.
• If the immediately previous student is shorter than the student before them, the next student must be taller than the immediately previous student.

In other words, the comparison between adjacent students must alternate at every position. For N = 5, arrangements such as 1 - 3 - 2 - 5 - 4 and 3 - 2 - 5 - 1 - 4 satisfy the condition.

Find the number of valid ways to arrange the N students.

The first line contains the number of students N. (1 <= N <= 100)

Print the number of valid arrangements modulo 1,000,000.