순열 교환

$1$부터 $n$까지의 수가 한 번씩 등장하는 크기 $n$짜리 순열을 생각한다.

교환 연산은 서로 다른 두 위치에 있는 수를 맞바꾸는 것이다. 한 순열에 교환 연산을 여러 번 적용해서 다른 순열을 만들 수 있고, 같은 자리를 여러 번 건드려도 된다.

순열 $A$가 주어진다. $1 \le k \le n-1$인 각 $k$에 대해, 교환 연산을 정확히 $k$번 써서 $A$를 만들 수 있는 순열이 몇 개인지 세는 프로그램을 작성하시오. 연산 횟수는 $k$번보다 적어도 안 되고 많아도 안 된다. 같은 순열은 한 번만 센다.

첫째 줄에 $n$이 주어진다. ($2 \le n \le 10^5$)

둘째 줄에 순열 $A$를 이루는 $n$개의 정수가 공백으로 구분되어 주어진다.

한 줄에 $n-1$개의 수를 공백으로 구분해 출력한다. $i$번째 수는 교환 연산을 정확히 $i$번 써서 $A$를 만들 수 있는 서로 다른 순열의 개수를 $10^9+7$로 나눈 나머지이다.

$n = 3$이고 $A = (3, 1, 2)$인 경우를 보자.

$(1, 3, 2)$, $(2, 1, 3)$, $(3, 2, 1)$은 교환 연산을 한 번 써서 $(3, 1, 2)$가 된다.

$(3, 1, 2)$, $(2, 3, 1)$, $(1, 2, 3)$은 교환 연산을 두 번 써서 $(3, 1, 2)$가 된다.