Description

给定一个排列 $p_1, \ldots, p_n$，它是数字 $1$ 到 $n$ 的一个排列。在每一步中，你可以选择两个数字 $x < y$ 并交换 $p_x$ 和 $p_y$。

设 $m$ 为将给定排列排序所需的最小交换次数。计算恰好用 $m$ 次交换来排序给定排列的不同序列的数量。由于这个数量可能很大，计算它对 $10^9 + 9$ 取模的结果。

Input Format

输入文件的第一行包含一个整数 $t$，表示测试用例的数量。每个测试用例前有一个空行。

每个测试用例由两行组成。第一行包含整数 $n$。第二行包含序列 $p_1, \ldots, p_n$：这是 $1, \ldots, n$ 的一个排列。

在简单子问题 C1 中，$1 \leq n \leq 10$。

在困难子问题 C2 中，$1 \leq n \leq 10^5$。

Output Format

对于每个测试用例，输出一行，包含一个整数：$x \bmod 10^9 + 9$，其中 $x$ 是用尽可能少的交换次数来排序给定序列的方法数。

3

3
2 3 1

4
2 1 4 3

2
1 2

3
2
1

Hint

在第一个测试用例中，我们可以通过两次交换来排序排列。我们可以任意进行第一次交换；对于每种情况，恰好有一种最佳的第二次交换。例如，三个最短解之一是“交换 $p_1$ 和 $p_2$，然后交换 $p_1$ 和 $p_3$”。

在第二个测试用例中，最佳解涉及交换 $p_1$ 和 $p_2$，以及交换 $p_3$ 和 $p_4$。我们可以以任意顺序进行这两次交换。

第三个序列已经排序。最佳交换次数为 $0$，因此唯一的最佳解是空的交换序列。

题目来源：IPSC2016

题面翻译由 ChatGPT-4o 提供。