Hide

# Problem IIndistinguishable Sequences

SoCCat the Group Theorist is a very detail-oriented cat. Currently, SoCCat is researching a unique equivalence relation on sequences!

SoCCat defines a map $L: \bigcup _{i\in \mathbb N} \mathbb Z^ i \to \mathbb N$ which takes in a sequence $\mathbf s = (s_1, s_2, \ldots , s_ k)$ of integers and outputs the length of a longest (strictly) increasing subsequence of $\mathbf s$.

Two sequences $\mathbf s = (s_1, s_2, \ldots , s_ k)$ and $\mathbf t = (t_1, t_2, \ldots , t_ l)$ are said to be indistinguishable if and only if they belong to the same fiber of the map $L$ – in other words, if $L(s_1, s_2, \ldots , s_ k) = L(t_1, t_2, \ldots , t_ l)$. That is, two sequences are indistinguishable if and only if the lengths of their longest increasing subsequences are the same.

SoCCat considers a very natural question: given a sequence $\mathbf a = (a_1, a_2, \ldots , a_ n)$, how many subsequences of $\mathbf a$ are indistinguishable from the original sequence $\mathbf a$ itself?

SoCCat doesn’t believe that you can do it, so they simply gave you a random permutation $\mathbf a$ for you to tinker with.

Surprise SoCCat by outputting the answer modulo $1\, 000\, 003\, 233$!

## Input

The first line of input contains an integer $n$, the length of the sequence ($1 \leq n \leq 100\, 000$).

The second line of input contains $n$ integers $a_1, a_2, \ldots , a_ n$, the integers in the permutation ($1 \leq a_ i \leq n$; $a_ i \neq a_ j$ if $i \neq j$). The permutation $\mathbf a$ is uniformly randomly generated from all $n!$ possible permutations.

## Output

Output a single integer, the number of subsequences of $\mathbf a$ that are indistinguishable from $\mathbf a$. In other words, output the number of subsequences of $\mathbf a$ such that the length of their longest increasing subsequence is equal to the length of the longest increasing subsequence of $\mathbf a$.

As the answer can be very large, output the answer modulo $1\, 000\, 003\, 233$.

## Notes

A sequence $\mathbf b$ is called a subsequence of another sequence $\mathbf a = (a_1,\ldots , a_ n)$ if there is a strictly increasing sequence of indices $i_1,\ldots , i_ p$ such that $\mathbf b = (a_{i_1},\ldots , a_{i_ p})$.

In the sample test case, we have $L(\mathbf a) = 2$, and any subsequences of $\mathbf a$ that belongs to the same fiber of $L$ as $\mathbf a$ must contain $a_2 = 1$, as well as either of $a_3$ or $a_4$ (or both).

Sample Input 1 Sample Output 1
4
4 1 3 2

6

Sample Input 2 Sample Output 2
10
2 4 8 7 3 9 5 6 1 10

84