Description

You are given a permutation $p_1,\cdots, 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. Compute the number of different sequences of exactly $m$ swaps that sort the given permutation. Since this number may be large, compute it modulo $10^9 + 9$.

Input Format

The first line of the input file contains an integer t specifying 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,\cdots, p_n$: a permutation of $1,\cdots, n$.

In the easy subproblem C1, $1 \leq n \leq 10$.

In the hard subproblem C2, $1 \leq n \leq 10^5$.

Output Format

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

3

3
2 3 1

4
2 1 4 3

2
1 2

3
2
1

Hint

In the first test case, we can sort the permutation in two swaps. We can make the first swap arbitrarily; for each of them, there's 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 involves swapping $p_1$ with $p_2$ and swapping $p_3$ with $p_4$. We can do these two swaps in either order.

The third sequence is already sorted. The optimal number of swaps is $0$, and thus the only optimal solution is an empty sequence of swaps.
题目来源：IPSC2016