Permutation Swaps

Consider a permutation of length $n$ in which every number from $1$ to $n$ appears exactly once.

A swap takes the numbers at two different positions and exchanges them. You can apply several swaps to a permutation to obtain another permutation, and you may touch the same position more than once.

A permutation $A$ is given. For each $k$ with $1 \le k \le n-1$, count the permutations that can be turned into $A$ with exactly $k$ swaps. Fewer than $k$ swaps and more than $k$ swaps both fail to count. Identical permutations are counted once.

The first line contains $n$. ($2 \le n \le 10^5$)

The second line contains the $n$ integers of the permutation $A$, separated by spaces.

Print $n-1$ numbers on one line, separated by spaces. The $i$-th number is the count of distinct permutations that can be turned into $A$ with exactly $i$ swaps, modulo $10^9+7$.

Take $n = 3$ and $A = (3, 1, 2)$.

Each of $(1, 3, 2)$, $(2, 1, 3)$, $(3, 2, 1)$ becomes $(3, 1, 2)$ after one swap.

Each of $(3, 1, 2)$, $(2, 3, 1)$, $(1, 2, 3)$ becomes $(3, 1, 2)$ after two swaps.