P4778 Counting swaps

Just like yesterday (in problem U of the practice session), Bob is busy, so Alice keeps on playing some single-player games and puzzles. In her newest puzzle she has a permutation of numbers from 1 to n. The goal of the puzzle is to sort the permutation using the smallest possible number of swaps. Instead of simply solving the puzzle, Alice is wondering about the probability of winning it just by playing at random. In order to answer this question, she needs to know the number of optimal solutions to her puzzle.

给定一个排列 $p_1, \ldots, p_n$，它是数字 $1$ 到 $n$ 的一个排列。在每一步中，你可以选择两个数字 $x < y$ 并交换 $p_x$ 和 $p_y$。 设 $m$ 为将给定排列排序所需的最小交换次数。计算恰好用 $m$ 次交换来排序给定排列的不同序列的数量。由于这个数量可能很大，计算它对 $10^9 + 9$ 取模的结果。

输入文件的第一行包含一个整数 $t$，表示测试用例的数量。每个测试用例前有一个空行。 每个测试用例由两行组成。第一行包含整数 $n$。第二行包含序列 $p_1, \ldots, p_n$：这是 $1, \ldots, n$ 的一个排列。 在简单子问题 C1 中，$1 \leq n \leq 10$。 在困难子问题 C2 中，$1 \leq n \leq 10^5$。

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

在第一个测试用例中，我们可以通过两次交换来排序排列。我们可以任意进行第一次交换；对于每种情况，恰好有一种最佳的第二次交换。例如，三个最短解之一是“交换 $p_1$ 和 $p_2$，然后交换 $p_1$ 和 $p_3$”。 在第二个测试用例中，最佳解涉及交换 $p_1$ 和 $p_2$，以及交换 $p_3$ 和 $p_4$。我们可以以任意顺序进行这两次交换。 第三个序列已经排序。最佳交换次数为 $0$，因此唯一的最佳解是空的交换序列。 题目来源：[IPSC2016](https://ipsc.ksp.sk/2016/real/problems/c.html) 题面翻译由 ChatGPT-4o 提供。