곤돌라 교체 수열 개수

마오콩 곤돌라는 타이페이의 유명한 관광 시설이다. 곤돌라 시스템은 원형 레일 위에 정류장 하나와, 1부터 $n$까지 번호가 붙은 $n$대의 곤돌라가 한 방향으로만 순환한다. $i$번 곤돌라가 정류장을 지나면 곧 $i+1$번이 지나가고, $n$번 다음에는 1번이 온다.

곤돌라가 고장나면 그 자리에 여분 곤돌라를 넣는다. 여분 곤돌라는 $n+1, n+2, \ldots$ 순으로 번호가 매겨지고, 항상 아직 쓰이지 않은 가장 작은 번호부터 사용한다. 예를 들어 $n=5$에서 1번이 고장나면 6번이 그 자리를 맡는다.

곤돌라 수열은 어떤 시점부터 정류장을 지나는 $n$대의 번호를 순서대로 적은 것이다. 기록을 시작하기 전에 이미 여러 번 고장과 교체가 있었을 수 있지만, 기록하는 동안에는 고장이 없다.

같은 배치라도 기록을 시작하는 시점에 따라 다른 곤돌라 수열이 나올 수 있다. 예를 들어 고장이 없고 $n=5$일 때 $(2,3,4,5,1)$과 $(4,5,1,2,3)$은 둘 다 가능하지만 $(4,3,2,5,1)$은 불가능하다.

교체 수열은 고장난 곤돌라 번호를 고장 순서대로 나열한 것이다. 교체 수열 $e$가 곤돌라 수열 $g$를 만든다는 것은, 초기 상태에서 $e$에 적힌 순서로 고장과 교체가 끝난 뒤 $g$가 가능한 곤돌라 수열이 되는 경우를 말한다.

길이 $n$의 수열이 주어질 때, 이 수열을 만들 수 있는 교체 수열의 개수를 $1\,000\,000\,009$로 나눈 나머지를 출력한다. 수열이 곤돌라 수열이 아니면 0을, 곤돌라 수열이지만 고장이 없었으면 1을 출력한다.

첫째 줄에 $n$이 주어진다.

둘째 줄에 수열의 $n$개 원소가 주어진다.

교체 수열의 개수를 $1\,000\,000\,009$로 나눈 나머지를 한 줄에 출력한다.