Hotel Branch Visitor Limit Assignment

A large hotel chain has 2025 branches numbered from 1 to 2025. For the upcoming holiday season, the head office wishes to assign a daily guest‐limit to each branch. Let the guest–limit for branch i be A_i (for i=1,2,…,2025). The assignment must be a permutation of the numbers 1 through 2025 (i.e. every integer in the range appears exactly once) and it must satisfy the following condition:

\(A_i \times A_j \le i \times j + 2025 \quad \text{for all} \; 1 \le i,j \le 2025. \)

This restriction is meant to balance the guest flow among branches. You are to calculate the number of possible assignments that satisfy the above conditions. Since the answer might be huge, output the answer modulo \(10^9+7\).

Note: After a careful analysis one can prove that a necessary and sufficient condition for a permutation \(A_1, A_2, \dots, A_{2025}\) to satisfy \(A_i\,A_j \le i\,j+2025\) for all \(i,j\) is that the assignment forces very small numbers in the early branches. In fact, by considering the pair \( (i,2025) \) for \(1 \le i \le 2024\) one may show that

\(A_i \le i+1 \quad \text{for} \; i=1,2,\dots,2024,\)

and since \(A_{2025}\) is the remaining number (and the permutation is over \(\{1,2,\dots,2025\}\) with \(2025\) as the maximum possible value), it turns out that the valid assignments are exactly those permutations in which for every \(k\) with \(1\le k\le2024\) the set \(\{A_1,A_2,\dots,A_k\}\) is a subset of \(\{1,2,\dots,k+1\}\).

A classic combinatorial argument shows that the number of such permutations is

\[ 2^{2025-1} \mod (10^9+7). \]
That is, the answer is \(2^{2024} \mod (10^9+7)\).

Input: This problem has no input.

Output: Output a single integer, the number of valid assignments modulo \(10^9+7\).

inputFormat

No input is given.

outputFormat

Output a single integer which is the number of valid assignments modulo \(10^9+7\).

sample

550920303