순열 교환

시간 제한2초메모리 제한512 MB

요약

각 k(1 이상 n-1 이하)마다 A에서 정확히 k번 교환해 얻을 수 있는 순열의 개수를 10^9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 조합론, 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

$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)$ 가 된다.

예제6

예제 1
입력
```
3
3 1 2
```
예상 출력
```
3 3
```
예제 2
입력
```
2
1 2
```
예상 출력
```
1
```
예제 3
입력
```
2
2 1
```
예상 출력
```
1
```
예제 4
입력
```
4
1 2 3 4
```
예상 출력
```
6 12 12
```
예제 5
입력
```
4
4 3 2 1
```
예상 출력
```
6 12 12
```
예제 6
입력
```
5
2 4 1 5 3
```
예상 출력
```
10 36 60 60
```