XIX математическая олимпиада «Шелковый путь», 2024 год

Пусть $n>1$ — целое число. В гостинице $n$ номеров, занумерованных числами $1,2,\dots,n$; в $i$-м номере $i$ комнат, при всех $i=1,2,\dots,n$. Каждую неделю в гостиницу заезжает очередная группа из $n$ семей; каждая семья заранее заявляет натуральное число — минимальное количество комнат в номере, которое ей необходимо. Перед каждым заездом, когда предыдущая группа выехала, портье подсчитывает количество $A$ способов выдать каждой семье по отдельному номеру так, чтобы все их требования были выполнены. Затем он записывает число $A$ в свою записную книжку. Докажите, что в записной книжке у портье есть не более $2^{n-1}$ различных ненулевых чисел. ( И. Богданов )