题目描述

给定一个 1∼$n$的排列 $p_1,p_2,…,p_n$，可进行若干次操作，每次选择两个整数 $x,y$，交换 $p_x,p_y$。

设把 $p_1,p_2,…,p_n$变成单调递增的排列 1,2,…,$n$ 至少需要$m$ 次交换。

求有多少种操作方法可以只用 $m$ 次交换达到上述目标。

因为结果可能很大，你只需要输出结果对$10^9$+9 取模之后的值。

例如排列 2,3,1 至少需要 2 次交换才能变为 1,2,3。

操作方法共有 3 种，分别是：

• 方法一：先交换数字 2,3，变成 3,2,1，再交换数字 3,1，变成 1,2,3。
• 方法二：先交换数字 2,1，变成 1,3,2，再交换数字 3,2，变成 1,2,3。
• 方法三：先交换数字 3,1，变成 2,1,3，再交换数字 2,1，变成 1,2,3。

输入格式

第一行包含整数 $T$，表示一共有 $T$组测试用例。

每个测试用例前都会有一个空行。

每个测试用例包含两行，第一行包含整数 $n$。

第二行包含$n$个整数，表示序列 $p_1,p_2,…,p_n$。

输出格式

每个测试用例输出一个结果，每个结果占一行。

样例

3

3
2 3 1

4
2 1 4 3

2
1 2

3
2
1

数据范围

$1≤n≤10^5$

来源

• 算法竞赛进阶指南