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