Counting swaps (Hard)

Just like yesterday (problem U of the practice session), Bob is busy, so Alice keeps playing single-player games and puzzles. In her newest puzzle, she has a permutation of the numbers 1 to $n$. The goal is to sort the permutation using the smallest possible number of swaps.

Instead of simply solving the puzzle, Alice wants to know the probability of winning by playing at random. To answer this, she needs the number of optimal solutions to the puzzle.

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

Let $m$ be the minimum number of such swaps needed to sort the given permutation. Count the number of different sequences of exactly $m$ swaps that sort the permutation. Since this number may be large, output it modulo $10^9 + 9$.

The first line contains an integer $t$, the number of test cases. Each test case is preceded by a blank line.

Each test case consists of two lines. The first line contains the integer $n$. The second line contains the sequence $p_1, \ldots, p_n$, a permutation of $1, \ldots, n$.

For each test case, output a single line containing one integer: $x \bmod (10^9 + 9)$, where $x$ is the number of ways to sort the given sequence using as few swaps as possible.

$1 \le n \le 10^5$

In the first test case, we can sort the permutation in two swaps. We can make the first swap in any way, and for each of them there is exactly one optimal second swap. For example, one of the three shortest solutions is "swap $p_1$ with $p_2$ and then swap $p_1$ with $p_3$".

In the second test case, the optimal solution swaps $p_1$ with $p_2$ and $p_3$ with $p_4$. These two swaps can be done in either order.

The third sequence is already sorted. The optimal number of swaps is 0, so the only optimal solution is the empty sequence of swaps.