2717. Counting swaps

【题目描述】

给定一个 $1~n$ 的排列 $p1,p2,…,pn$，可进行若干次操作，每次选择两个整数 $x,y$，交换 $px,py$。

设把 $p1,p2,…,pn $变成单调递增的排列$ 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个整数，表示序列$p1,p2,…,pn$。

【输出格式】

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

【样例输入】

3

3
2 3 1

4
2 1 4 3

2
1 2

【样例输出】

3
2
1

【提示】

$1≤n≤10^5$

【来源】

【IPSC 2016】