Calvinball championship

This year the Czech Republic hosts a Calvinball championship. The rules of Calvinball are left aside here; only the way teams are chosen and recorded matters.

One game of Calvinball is played by $n$ players with distinct names, split into any number of non-empty teams. The split is recorded like this. In each team, the player whose name is lexicographically smallest becomes the captain. The teams are then sorted by the names of their captains in lexicographic order and numbered 1, 2, 3 and so on. Finally the players are listed in lexicographic order of their names, each with the number of the team it belongs to.

For example, with three teams, one holding Calvin, Hobbes and Susie, one holding Tom and Jerry, and one holding only Batman, the record is:

Batman 1
Calvin 2
Hobbes 2
Jerry 3
Susie 2
Tom 3

The same players play every day of the championship, and only the split changes. Since the players never change, the names are dropped and the record is written as the sequence of team numbers alone. The example above becomes 1 2 2 3 2 3. The championship ends once every possible split has been used, one per day.

The days follow the lexicographic order of these sequences. On the first day everybody is on one team, so the sequence is 1 1 1 1 1 1. On the second day Tom plays against everybody else, so the sequence is 1 1 1 1 1 2. On the last day everybody plays against everybody, so the sequence is 1 2 3 4 5 6.

Given one record, determine the day of the championship on which it is used. Print that number modulo 1000007.

The names in the example are there for the explanation only and play no role in the task.

The first line contains the number of players $n$ ($1 \le n \le 10000$).

The second line contains $n$ team numbers separated by spaces. The sequence is always a valid record built by the rules above, so the first number is 1 and every number is at most one more than the largest number before it.

Print one line with the day of the championship on which the given split is used, modulo 1000007. The first day of the championship is day 1.

With three players the possible splits are 1 1 1, 1 1 2, 1 2 1, 1 2 2, 1 2 3.