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

输出格式

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

数据范围

$1 \le n \le 10^5$

输入样例：

3

3
2 3 1

4
2 1 4 3

2
1 2

输出样例：

3
2
1

来源

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