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:

**solution**

My only question: why we can keep the factor 2 by `mod 2*(mod-1)`

? Thanks in advance