Coins

Bajtazar is very proud of his collection of rare coins. He has gathered them over many years, making sure that no two are alike. He currently owns $n$ coins, numbered so that the $i$-th coin has size exactly $i$.

Because his collection has grown, Bajtazar bought a new coin album. It has exactly $n$ slots for coins, each with a fixed size. A coin cannot be placed in a slot that is too small for it, but it may be placed in a larger slot. Each slot holds exactly one coin, and every coin must be placed.

Bajtazar now wonders which slot to put each coin in, and in how many different ways he can fill the whole album. Because this number can be very large, it is enough to report it modulo $10^9 + 7$. Write a program that computes this number.

The first line contains one integer $n$ ($1 \le n \le 10^6$). The second line contains $n$ integers $a_i$ ($1 \le a_i \le n$) separated by single spaces. The value $a_i$ is the size of the largest coin that can be placed in the $i$-th slot; that slot can therefore hold any coin whose size is at most $a_i$.

Print one integer: the number of ways to fill the album, modulo $10^9 + 7$.