Calvinball championship
In addition to CEOI and ice hockey championship, Czech Republic hosts this year also a Calvinball championship. We will not go into the quasiexistent rules of Calvinball, and instead focus on the team selection procedure.
A game of Calvinball is played by n players with distinct names, divided into any number of non-empty teams. To record the teams, the following convention is employed. First, the player in each team with the lexicographically smallest name is chosen as the captain of the team. Then, the teams are sorted lexicographically by the names of their captains and numbered by consecutive integers starting from 1. Finally, the players are listed in the lexicographic order together with their team numbers.
For example, if there are three teams, one consisting of Calvin, Hobbes, and Susie, one consisting of Tom and Jerry, and one consisting only of Batman, the record would look like this:
Batman 1
Calvin 2
Hobbes 2
Jerry 3
Susie 2
Tom 3
The same players play each day of the championship, but each time, different teams are chosen. As the players arethe same each day, we can for briefness omit their names from the listing and record the teams only as the sequence of team numbers (1 2 2 3 2 3 in the above example). The championship ends when all the possible team choices were tried out.
As there are many possible team choices, deciding the teams for each day used to be quite confusing. This year, the International Calvinball Disorganization decided that the team selections will be made according to the lexicographic ordering of the sequences that represent them. So, the first day, all players will be on the same team (sequence 1 1 1 1 1 1), the second day everybody plays against Tom (sequence 1 1 1 1 1 2), . . . , and on the last day, everybody plays against everybody (sequence 1 2 3 4 5 6).
For a given record of teams, determine on which day of the tournament it will be used. Output the number modulo1000007.
Please note that the names of the players in the example are for the sake of explanation only and they play no role in the actual task.
Input
The first line contains a positive integer n (1 ≤ n ≤ 10000). The second line contains n positive integers separated by spaces, giving the description of teams as specified in the task statement.
Output
Print a single integer giving the number of the day of the championship on which the given team selection will be used modulo 1000007. The first day of the championship has number 1.