The Book Exchange Ceremony

In a grand ceremony, 'N' scholars, each holding a unique book, are to exchange their books among themselves.

A valid exchange is a permutation of books where any scholar is part of an exchange cycle of at most length 3. This means a scholar can either:

1) Keep their own book (a cycle of length 1).

2) Swap books with one other scholar (a cycle of length 2).

3) Participate in a three-way exchange (a cycle of length 3).

Your task is to find the total number of distinct, valid book exchange arrangements possible for 'N' scholars. Since the number can be very large, you must return the result modulo 1,000,000,007.

Input Format:

A single line containing an integer 'N'.

Output Format:

Print a single integer representing the total number of valid arrangements modulo 1,000,000,007.

Note:

This problem can be solved using a recurrence relation (Dynamic Programming).
Let dp[i] be the number of valid arrangements for i scholars. We can form the arrangement for i scholars by considering the i-th scholar:
  1) Case 1: The i-th scholar keeps their own book (1-cycle). The remaining i-1 scholars can be arranged in dp[i-1] ways.
  2) Case 2: The i-th scholar swaps with one of the i-1 other scholars (2-cycle). There are i-1 choices for the swap partner. The remaining i-2 scholars can be arranged in dp[i-2] ways.
  3) Case 3: The i-th scholar joins a 3-cycle with two of the i-1 other scholars. There are (i-1) * (i-2) ways to choose two other scholars in a specific order for a 3-cycle. The remaining i-3 scholars can be arranged in dp[i-3] ways.