Calvinball Championship

Problem Statement: There are \(n\) players numbered \(1,2,\dots,n\) participating in a Calvinball championship. They form a set partition into nonempty teams. The teams are ordered in increasing order of the minimum player number in each team and are renumbered consecutively starting from 1.

A team record is given as a sequence \(a_1, a_2, \dots, a_n\) of positive integers satisfying the restricted growth function conditions:

• \(a_1 = 1\);
• For every \(i \ge 2\), \(a_i \in \{1,2,\dots,\max(a_1,a_2,\dots,a_{i-1})+1\}\).

Each valid record corresponds to a legal team formation. All possible records are ordered lexicographically. The championship schedule is determined by this lexicographical order: the first day uses the lexicographically smallest record, the second day uses the next record, and so on.

Given a valid team record, compute the day on which the record will be used. Since the number can be large, output the answer modulo \(1\,000\,007\).

Note: The day numbering starts at 1.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) (the number of players).
2. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the team record. It is guaranteed that \(a_1=1\) and for every \(i\ge2\), \(a_i \in \{1,2,\dots,\max(a_1,a_2,\dots,a_{i-1})+1\}\).

outputFormat

Output a single integer — the day (i.e. the lexicographical rank of the record among all valid records) on which the record will be used, modulo \(1\,000\,007\).

sample

5
1 1 1 1 1

1