411 : 登り坂軌道

ある正の整数を$n$とする。$0\leq i \leq 2n$において座標$(x, y) = (2^i \mod n, 3^i \mod n)$の位置に駅があるとしよう。同じ座標を持つ駅が複数できる場合、それらは同じ駅であると見なす。

$(0, 0)$から$(n, n)$まで、$x, y$座標がいずれも減少することのない軌道を作ってみよう。そのような軌道で通ることのできる駅の最大数を$S(n)$とする。

例えば$n=22$の場合、11個の駅があり、条件を満たす軌道は最大5駅を通ることができる。したがって $S(22) = 5$となる。最適な軌道の例と共に、下にこの例を図示する。

$S(123) = 14, S(10000) = 48$であることが確かめられる。

$1 ≤ k ≤ 30$における$\sum S(k^5)$を求めよ。