题目描述

给定一个 $1\sim 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$。

输出格式

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

数据范围

$1 \le n \le 10^5$

输入样例：

3

3
2 3 1

4
2 1 4 3

2
1 2

输出样例：

3
2
1

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解