Knights’ Teleportation Cycle

The Blue Kingdom has \(42\) cities and \(42\) knights. The knights are numbered from \(1\) to \(42\) and knight \(i\) initially resides in city \(i\). A new teleportation device is introduced which uses a permutation \(a=(a_1, a_2, \ldots, a_{42})\) of the numbers \(1,2,\dots,42\). When activated, the knight in city \(i\) is teleported to city \(a_i\).

For testing purposes, the kingdom will perform this teleportation for \(2024\) consecutive days using the same permutation \(a\) each day. Design a permutation \(a\) such that:

• After exactly \(2024\) days, every knight returns to his starting city.
• For any day before \(2024\), not all the knights are simultaneously back in their initial cities.

In other words, if we define the order of the permutation \(a\) to be the minimum positive integer \(k\) for which applying \(a\) \(k\) times returns every knight to his original city, you are required to have \(\mathrm{order}(a)=2024\).

Note on Permutations: The permutation \(a\) is a sequence containing each of the numbers \(1, 2, \ldots, 42\) exactly once. Two permutations are considered different if there is at least one position at which they differ.

Hint: A permutation decomposes into disjoint cycles. The condition \(\mathrm{order}(a)=2024\) means that the least common multiple of the cycle lengths in the permutation is exactly \(2024\). Factoring \(2024\) gives \(2024 = 2^3 \times 11 \times 23\). Given that the sum of all cycle lengths must be \(42\), it turns out the only possibility is to have exactly three cycles of lengths \(8\), \(11\) and \(23\) (since \(8+11+23=42\)). The number of valid permutations is therefore \[ \frac{42!}{8\cdot 11\cdot 23} \quad (\mathrm{mod} \; 10^9+7). \]

inputFormat

This problem does not require any input.

outputFormat

Output a single integer: the number of valid permutations \(a\) (mod \(10^9+7\)).

sample

N/A

774554175