A school has n students numbered 1..n and n lockers numbered 1..n. Each student gets exactly one
locker. Student s is happy with locker p only if p divides s or s divides p. Return how many
ways there are to hand out the lockers so that every student is happy.
Examples
Input: n = 3
Output: 3
Explanation: (locker 1, 2, 3 go to students) [1, 2, 3], [2, 1, 3] and [3, 2, 1].
Students 2 and 3 can never swap, since neither 2 nor 3 divides the other.
Input: n = 1
Output: 1
Input: n = 2
Output: 2
Constraints
1 <= n <= 12
Goals
- Count permutations that satisfy a per-position rule
- Check the rule as each element is placed, not at the end