Problem link: Here

Harder version of problem: Here

The best way I could think of right now is factorizing using pollard rho and then do O(N*D) dp where D is number of divisors. Problem is D can be up to almost 10^5 for some highly composite numbers.

Another idea that comes to mind is to treat divisors as vertex, connect them if they can be adjacent in the resulting sequence, and find total number of walks with length (n-1) which can be done using matrix power. But this seems even slower because matrix can be large.

Any help is appreciated, thanks!