Gondola replacement count

The Maokong Gondola in Taipei runs on a circular rail with one station and $n$ gondolas numbered 1 through $n$ that move in a single direction. After gondola $i$ passes the station, gondola $i+1$ passes next, and after $n$ comes 1 again.

When a gondola breaks, it is replaced at the same position by a spare. Spares are numbered $n+1, n+2, \ldots$ and the smallest unused spare is always chosen. For example, with $n=5$, if gondola 1 breaks, spare 6 takes its place.

A gondola sequence lists the $n$ consecutive gondola numbers seen at the station starting from some moment. Breakdowns may have happened before recording starts, but none occur while the sequence is recorded.

The same physical setup can yield different gondola sequences depending on when you start recording. With no breakdowns and $n=5$, both $(2,3,4,5,1)$ and $(4,5,1,2,3)$ are possible, but $(4,3,2,5,1)$ is not.

A replacement sequence lists the numbers of gondolas that broke, in breakdown order. Replacement sequence $e$ creates gondola sequence $g$ if, starting from the initial setup, after all breakdowns and replacements described by $e$, $g$ is a possible gondola sequence.

Given a sequence of length $n$, output the number of replacement sequences that could create it, modulo $1\,000\,000\,009$. Output 0 if the sequence is not a gondola sequence, and 1 if it is a gondola sequence with no breakdowns.

The first line contains $n$.

The second line contains the $n$ integers of the sequence.

Print one integer, the count modulo $1\,000\,000\,009$.