Coins

Interview

Time limit1sMemory limit512 MB

Summary

Count the ways to place coins of sizes 1 to n into slots with capacities a_i so every coin fits, modulo 1000000007.

Level: Medium4 of 10
Topics: Sorting, Combinatorics, Greedy
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Examples4

Example 1
Input
```
4
4 2 4 2
```
Expected output
```
4
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
2
2 2
```
Expected output
```
2
```
Example 4
Input
```
3
3 3 3
```
Expected output
```
6
```