RU-ALLRUSSIAN 2016 Problem 116

There are $n>1$ cities in the country, some pairs of cities linked two-way through straight flight. For every pair of cities there is exactly one aviaroute (can have interchanges). Major of every city X counted amount of such numberings of all cities from $1$ to $n$ , such that on every aviaroute with the beginning in X, numbers of cities are in ascending order. Every major, except one, noticed that results of counting are multiple of $2016$ . Prove, that result of last major is multiple of $2016$ too.