The following problem was adapted from VBlunder by totallyAugustus.

An unnamed Grade 9 student at A. M. Johnson Secondary School is attempting to fast track using OVS courses so that they can take an obscene number of 4U courses and stack their top 6. They have asked you to tell them all possible course subsets they can purchase.

Given \(N\) courses offered by OVS, with the \(i^{th}\) course allowing up to \(a_i\) additional concurrent courses, calculate how many different subsets of courses they can simultaneously enroll in.

Note: The student has asked you include at least one course in each subset.

Constraints

\(1 \le N \le 10^5\)

\(0 \le a_i \le N - 1\)

Input Specification

The first line contains \(N\).

The second line contains \(N\) integers, \(a_i\).

Output Specification

Output one integer, the number of different subsets of courses he can take. Since this number can be incredibly large, output it modulo \(\text{1 000 000 007}\).

Sample Input

3
0 1 1

Sample Output

4

Explanation for Sample Output

Assuming a one-indexed array, the four subsets are \(\{1\}, \{2\}, \{3\}, \{2,3\}\)