The way to solve this problem is easy. Just let $$$n=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$$$ ($$$p_i$$$ are pairwise different) then the answer will be
There're more than one way to get ans (a simple way is to use prefix product). But today I read a solution which I could not understand:
My only question: why we can keep the factor 2 by mod 2*(mod-1)
? Thanks in advance