Problem Description

Translated from CEOI2015 Day1 T2 “Calvinball championship”.

A Calvinball match has $n$ players participating, numbered $1 \dots n$, and they are divided into several non-empty teams. We define the order of teams by sorting them according to the smallest player number in each team, and then numbering the teams with consecutive integers starting from $1$.

For example, suppose player $1$ forms a team alone; players $2, 3,$ and $5$ form a team; and players $4$ and $6$ form a team.

> $\ \texttt{1}$
> $\ \texttt{2 3 5}$
> $\ \texttt{4 6}$

Then player $1$’s team is team $1$, player $2$’s team is team $2$, and player $4$’s team is team $3$.

> $\ \texttt{1|1}$
> $\ \texttt{2|2 3 5}$
> $\ \texttt{3|4 6}$

Each day, everyone will choose a different team partition. When recording, we can omit the player numbers and only record the sequence of team numbers that each position belongs to (in the above example, 1 2 2 3 2 3), because the players are the same every day. The championship ends when all possible choices have been used.

Since there are too many choices, indecisive people find it hard to handle. This year, we decide to choose the partitions according to the lexicographical order of the recorded sequences. Therefore, on the first day, everyone is in one team: 1 1 1 1 1 1; on the second day, everyone opposes player $6$: 1 1 1 1 1 2; … on the last day, everyone is in their own team: 1 2 3 4 5 6.

Given a recorded team sequence, compute on which future day this record will be used. Output this number modulo $1\ 000\ 007$.

Input Format

The first line contains a positive integer $n(1 \leq n \leq 10\ 000)$.

The second line contains $n$ positive integers separated by spaces, representing the team record given in the task.

Output Format

Output a positive integer: the day on which the given team record will be used, modulo $1\ 000\ 007$. The first day is numbered $1$.

3
1 2 2

4

Hint

Please note that for a three-player match, the possible choices are 1 1 1, 1 1 2, 1 2 1, 1 2 2, and 1 2 3.

Constraints and Hints

Translated by ChatGPT 5