시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 132 | 63 | 59 | 53.153% |
민돌(mindol)의 이름을 들어 본 적이 있는가? 세계 최고의 래퍼인 민돌은 100개국 투어로 번 돈으로 얼마 전 놀이공원 민돌 파크를 세웠다.
민돌 파크의 명물은 트램펄린 놀이기구로, $0$번, $1$번, ..., $N$번까지 총 $N+1$개의 트램펄린이 순서대로 놓여 있어 트램펄린 사이를 뛰어다니면서 즐기는 놀이기구이다. $0$번 트램펄린은 시작 지점으로, 다른 모든 트램펄린으로 한 번에 뛰어갈 수 있다. $i$번 트램펄린 ($1 \le i \le N$) 에서는, 번호 차이가 $A_i$ 이하인 트램펄린까지만 한 번에 뛰어갈 수 있다. 안전을 위해, 모든 트램펄린에서 $0$번 트램펄린까지 한 번에 뛰어갈 수 있도록 되어 있다. 즉, $A_i \ge i$이다.
민돌의 열렬한 팬이었던 민솔이는 이 소식을 듣고 곧바로 민돌 파크에 놀러 갔다. 민솔이는 트램펄린 놀이기구를 뭔가 특별한 방법으로 타고 싶었는데, '해밀턴'이 '민돌'과 라임이 맞는다고 생각한 민솔이는 해밀턴 투어를 본딴 민돌 투어를 해 보기로 했다. 민돌 투어란, $0$번 트램펄린에서 시작해 다른 모든 트램펄린을 정확히 한 번씩 방문하고 다시 $0$번 트램펄린으로 돌아오는 것을 말한다.
민솔이는 가능한 모든 민돌 투어를 한 뒤 집으로 돌아가려 한다. 민솔이는 놀이기구를 몇 번 이용해야 할까?
첫 번째 줄에 $0$번 트램펄린을 제외한 트램펄린의 개수 $N$ ($1 \le N \le 200\, 000$) 이 주어진다.
두 번째 줄에는 $N$개의 정수 $A_i$ ($i \le A_i \le N$) 들이 공백을 사이에 두고 주어진다.
첫 번째 줄에 모든 가능한 민돌 투어의 수를 $10^9+7$로 나눈 나머지를 출력한다.
3 1 3 3
4
5 5 5 5 5 5
120
첫 번째 예제의 경우 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0$ / $0 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 0$ / $0 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 0$ / $0 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 0$의 4가지 투어가 가능하다.
High School > 경기과학고등학교 > 나는코더다 2017 송년대회 C번