Observing the range of \(n\) , we find it impossible to count all the sequence . In common situations , we should use DP to solve this kind of problem . However , to this one , we should consider it as a graph problem .

First , we find if we start from \(i\) and keep moving to \(a_i\) , we will be moving on a chain and in the end , we will be trapped in a circle . So it’s natural to add an edge from \(i\) to \(a_i\) . It’s widely known that if \(a\) is a permutation of \(n\) , the graph will be a combination of a couple of circles . What will happen if some numbers repeat in the sequence for several times ?

Well , it will still be a combination of a couple of circles. However , the other vertexes which are not in the circles , will point to the circles . we call it 基环树森林 in Chinese .

OK , now we build the graph successfully , but how to calculate the answer ? we can easily find that if the distance between a vertex and the nearest circle is \(d\) , the answer starting from it will be \(d\) , \(d=0\) when the vertex is in a certain circle.

The final result is \(\sum_{G} \sum_{i=1}^{n} d_i \) . It’s obvious that different i s are just the same . So we can make \(i\) equals to \(1\) , and output \(n\) times of the answer in the end .

What’s more , we can enumerate different \(d\) , and count how many graphs there are to meet the condition . There is a chain from \(1\) to the circle , whose length is \(d\) excluding \(1\) but including the last one in a circle . The number of the chains is \(A_{n-1}^d\) . And if the last one is in a circle size of \(S\) , there will be \(C_{n-k-1}^{s-1} (s-1)!=A_{n-k-1}^{s-1}\) kinds of such circle . And , for the vertexes that haven’t been counted yet , their \(a\) is arbitrary , so it’s \(n^{n-k-s}\) . We should just calculate \(\sum_{s=1}^{n-k} A_{n-k-1}^{s-1}n^{n-k-s}\) .

When \(k=n\) , the answer is evidently \(0\) . If we calculate \(k\) , what about \(k-1\) ?

\[\sum_{s=1}^{n-k+1} A_{n-k}^{s-1}n^{n-k-s+1}\]

\[= n^{n-k}+\sum_{s=2}^{n-k+1} A_{n-k}^{s-1}n^{n-k-s+1}\]

\[=n^{n-k}+(n-k)\sum_{s=2}^{n-k+1} A_{n-k-1}^{s-2}n^{n-k-s+1}\]

\[=n^{n-k}+(n-k)\sum_{s=1}^{n-k} A_{n-k-1}^{s-1}n^{n-k-s}\]

You see , the right part of the equation has been calculated already , so you can just enumerate \(k\) in a reverse order and output \(n \sum_{k=1}^{n-1} k \times array_k \times A_{n-1}^k \) in the end .

I’m afraid that I may make a few mistakes in the article , please forgive me for my weak English.

A very short code :

#include<bits/stdc++.h>
long long n,m,r,k=1,p=1,s[200010];
int main() {
    std::cin>>n>>m;
    for(int v=n-1;v;v--) s[v]=(s[v+1]*(n-v-1)+p)%m,p=p*n%m;
    for(int v=1;n-v;v++) k=k*(n-v)%m,r=(r+k*s[v]%m*v)%m;
    std::cout<<r*n%m;
}