캘빈볼 선수권

올해 체코에서 캘빈볼 선수권 대회가 열린다. 캘빈볼의 규칙 자체는 다루지 않고, 팀을 나누고 기록하는 방법만 설명한다.

한 판의 캘빈볼에는 이름이 서로 다른 $n$명의 선수가 참가하고, 선수 전원을 비어 있지 않은 팀 여러 개로 나눈다. 팀의 개수에는 제한이 없다. 팀 구성은 다음 규칙으로 기록한다. 먼저 각 팀에서 이름이 사전순으로 가장 앞서는 선수를 그 팀의 주장으로 정한다. 다음으로 주장의 이름을 사전순으로 비교해 팀을 정렬하고, 앞에서부터 1번, 2번, 3번과 같이 번호를 붙인다. 마지막으로 선수를 이름의 사전순으로 나열하면서 각 선수가 속한 팀의 번호를 함께 적는다.

예를 들어 팀이 세 개이고 각각 Calvin, Hobbes, Susie로 이루어진 팀과 Tom, Jerry로 이루어진 팀, Batman 혼자인 팀이라면 기록은 다음과 같다.

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

대회 기간 내내 선수는 그대로이고 날마다 팀만 다시 나눈다. 선수가 매일 같으므로 이름은 생략하고 팀 번호의 수열만 적어도 된다. 위 예는 1 2 2 3 2 3이 된다. 가능한 팀 나누기를 하루에 하나씩 모두 써 보면 대회가 끝난다.

날짜의 순서는 이 수열의 사전순으로 정한다. 첫날에는 전원이 한 팀이 되고 수열은 1 1 1 1 1 1이다. 둘째 날에는 Tom 혼자 나머지 전원과 겨루어 수열이 1 1 1 1 1 2가 된다. 마지막 날에는 모두가 서로를 상대하므로 수열은 1 2 3 4 5 6이다.

기록이 하나 주어지면 그 기록이 대회 며칠째에 쓰이는지 구하여라. 답은 1000007로 나눈 나머지를 출력한다.

예에 나오는 이름은 설명을 위한 것일 뿐 문제 풀이와는 상관이 없다.

첫째 줄에 선수의 수 $n$이 주어진다 ($1 \le n \le 10000$).

둘째 줄에 팀 번호 $n$개가 공백으로 구분되어 주어진다. 이 수열은 문제에서 설명한 방식으로 만든 올바른 기록이므로, 첫 번째 수는 1이고 각 수는 앞에 나온 수의 최댓값보다 1만큼 큰 값을 넘지 않는다.

주어진 팀 나누기가 대회 며칠째에 쓰이는지를 1000007로 나눈 나머지를 한 줄에 출력한다. 대회 첫날이 1일째이다.

선수가 3명일 때 가능한 팀 나누기는 1 1 1, 1 1 2, 1 2 1, 1 2 2, 1 2 3이다.