Пусть n будет натуральным числом. Представьте, что в координатах (x, y) = (2ⁱ mod n, 3ⁱ mod n) для 0 ≤ i ≤ 2n расположены станции. Будем считать станции с одинаковыми координатами одной и той же станцией.

Мы хотем проложить через существующие станции путь из (0, 0) в (n, n), причем такой, в котором координаты x и y никогда не уменьшаются.
Пусть S(n) будет максимальным количеством станций, через которые такой путь может пройти.

Например, если n = 22, существует 11 различных станций, и удовлетворяющий условию путь может пройти через максимум 5 станций. Посему, S(22) = 5. Этот случай проиллюстрирован ниже примером оптимального пути:

Можно также показать, что S(123) = 14 и S(10000) = 48.

Найдите ∑ S(k⁵) для 1 ≤ k ≤ 30.