Подорож

У деякій країні $n$ міст, пронумерованих від $1$ до $n$. Мандрівник на початку знаходиться у $1$-му місті і хоче побувати в усіх містах країни. Відомо, що він діє за наступним алгоритмом: спочатку випадковим чином вибирається ціле число $m$ з відрізку [1, n - 1]. Після цього міста відвідуються у порядку 1,\ 1 + m \bmod n,\ 1 + (2 \cdot m) \bmod n,\ \ldots і так далі, доки не потрапить у вже відвідане місто. Відмітимо, що цей процес завжди буде скінченним, так як множина міст скінченна. Знайдіть ймовірність того, що мандрівник відвідає усі міста країни.