동전

Bajtazar는 자신의 희귀 동전 컬렉션을 매우 자랑스러워합니다. 그는 오랜 세월 동안 어떤 두 동전도 서로 같지 않도록 신경 쓰며 동전을 모았습니다. 현재 그는 $n$개의 동전을 가지고 있으며, $i$번째 동전의 크기가 정확히 $i$가 되도록 번호가 매겨져 있습니다.

컬렉션이 커지면서 Bajtazar는 새 동전첩을 샀습니다. 이 동전첩에는 동전을 넣는 칸이 정확히 $n$개 있고, 각 칸에는 정해진 크기가 있습니다. 어떤 동전도 자신보다 작은 칸에는 넣을 수 없지만, 더 큰 칸에는 넣을 수 있습니다. 각 칸에는 정확히 한 개의 동전이 들어가며, 모든 동전을 넣어야 합니다.

이제 Bajtazar는 각 동전을 어느 칸에 넣을지, 그리고 동전첩 전체를 채우는 방법이 몇 가지인지 궁금합니다. 이 수가 매우 클 수 있으므로 $10^9 + 7$으로 나눈 나머지만 구하면 됩니다. 이 값을 계산하는 프로그램을 작성하세요.

첫째 줄에 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다. 둘째 줄에는 $n$개의 정수 $a_i$ ($1 \le a_i \le n$)가 공백 하나로 구분되어 주어집니다. $a_i$는 $i$번째 칸에 넣을 수 있는 가장 큰 동전의 크기입니다. 즉, 그 칸에는 크기가 $a_i$ 이하인 동전을 넣을 수 있습니다.

동전첩을 채우는 방법의 수를 $10^9 + 7$으로 나눈 나머지를 정수 하나로 출력하세요.