Zigzag Lineup

Time limit2sMemory limit128 MB

Summary
Count permutations of N distinct heights where adjacent comparisons strictly alternate, modulo 1,000,000.
Level

Medium6 of 10

Topics
Dynamic programming, Combinatorics, Math
Solved
No attempts yet

Problem

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.

Input

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

Output

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

Examples1

  1. Example 1

    Input
    5
    Expected output
    32