№ 13823

В стране есть $n\gt 1$ городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между любыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города $X$ подсчитал количество таких нумераций всех городов числами от 1 до $n$, что на любом авиамаршруте, начинающемся в $X$, номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчётов делятся на 2016. Докажите, что и у оставшегося мэра результат также делится на 2016.