This problem is very similar to https://atcoder.jp/contests/abc180/tasks/abc180_f

As we can deduce from the statement, the graph of a valid permutation with edges from \(i\) to \(p_i\) will consists of many cycles.

If we have a group of \(n\) vertices and we have to construct a cycle from them, then there will be \(n!\) permutations possible. But given that for each permutation, we are also overcounting their cyclic shifts. Therefore \((n - 1)!\) possible cycles will be formed using \(n\) vertices.

For a cycle with \(n\) vertices, it can be seen that all balls will be in its place after every \(n*d\) operations with \(d > 0\). Therefore, the final answer should divides every possible size from cycles while is also minimum. From that, we can deduce that the answer is \(LCM\) of all sizes from every cycle.

Let \(DP[i][j]\) be the number of ways to assign values to \(i\) people out of \(N\) people so that \(LCM\) of all cycles is currently \(j\). The transition is as follow:

\[DP[i + x][LCM(j, x)] \mathrel{{+}{=}} DP[i][j] * \binom{n-i-1}{x-1} * (x-1)!\]

It means that we try to pick a group of \(x\) people to form the next cycle. However, to ensure that we won’t have repetition, we should always pick a person that hasn’t been chosen yet and has the smallest number. Hence, it left us with \(x-1\) options left from \(n-i-1\) remaining people.

The base case is \(DP[0][1]\) = 1.

However, since the second dimension can get very large (but still fit the int64), we can use a data structure like std::map to store the DP states.

The final answer is \(\sum DP[n][s]*s^k\) .

Sample code: https://atcoder.jp/contests/abc226/submissions/27123387