这道题乍一看挺水的，直接$ Ploya $就可以了，可是再看看数据范围：n<=1e9
那就是有1e9种置换，这不歇比了。
于是考虑式子的优化。
首先证明，转i次的置换的每个循环结大小是 $ gcd(i,n) $
证明：
首先设第x个元素的位置是p，置换种类是i，循环k次后回到原点，k也就是循环结个数。
$ ik+p equiv p (mod n) $
$ ik equiv 0 (mod n) $
$ n|ik $
$ i|ik $
我们要让k最小，那么：
$ ik=lcm(i,n) $
$ ik= frac{in}{gcd(i,n)} $
$ k= frac{n}{gcd(i,n)} $
每个循环结都一样大，所以循环结个数是：
$ num= frac{n}{frac{n}{gcd(i,n)}} =gcd(i,n) $
证毕。
接着推polya的式子：
[s]是单位函数，s成立返回1，否则返回0。
$ans=frac{1}{n} sum limits_{i=1}^n n^{gcd(i,n)} $
$ =sum limits_{i=1}^n n^{gcd(i,n)-1} $
$ =sum limits_{i=1}^n sum limits_{d|n} n^{d-1} $
$ =sum limits_{d|n} n^{d-1} sum limits_{i=1}^n [gcd(i,n)==d] $
$ =sum limits_{d|n} n^{d-1} sum limits_{i=1}^{frac{n}{d}}[gcd(i,frac{i}{n})==1]$
$ =sum limits_{d|n} n^{d-1} phi{(frac{n}{d})} $
可以分解质因子然后dfs遍历所有因数，顺便求出欧拉函数。
问题解决。