Counting Minimal Swap Sequences

You are given a permutation \(p_1, p_2, \dots, p_n\) of the numbers 1 through n. In each step you can choose two indices \(x < y\) and swap \(p_x\) with \(p_y\).

Let \(m\) be the minimum number of swaps needed to sort the given permutation. It is well-known that \(m = n - c\), where \(c\) is the number of cycles in the permutation. Moreover, one can prove that the number of different sequences of exactly \(m\) swaps that sort the permutation is \(m!\) (factorial of \(m\)). Since the answer can be very large, output it modulo \(10^9+9\).

Input: The first line contains an integer \(n\) (the size of the permutation). The second line contains \(n\) space-separated integers representing the permutation.

Output: Output a single integer: the number of different sequences of exactly \(m\) swaps that sort the permutation, modulo \(10^9+9\).

inputFormat

The input consists of two lines. The first line contains an integer \(n\) denoting the number of elements in the permutation. The second line contains \(n\) space-separated integers \(p_1, p_2, \dots, p_n\) which represent a permutation of the numbers 1 through \(n\).

outputFormat

Output a single integer: the number of different sequences of swaps (of minimal length) that sort the permutation, computed modulo \(10^9+9\).

sample

3
2 1 3

1