题目描述

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

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

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

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

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

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

1. 先交换数字 $2,3$，变成 $3,2,1$，再交换数字 $3,1$，变成 $1,2,3$。
2. 先交换数字 $2,1$，变成 $1,3,2$，再交换数字 $3,2$，变成 $1,2,3$。
3. 先交换数字 $3,1$，变成 $2,1,3$，再交换数字 $2,1$，变成 $1,2,3$。

输入格式

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

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

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

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

输出格式

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

样例

输入样例：

3

3
2 3 1

4
2 1 4 3

2
1 2

输出样例：

3
2
1

样例解释

第一组数据：$n=3$，排列为 $2,3,1$。
至少需要 $2$ 次交换，有 $3$ 种方法，如题目描述。

第二组数据：$n=4$，排列为 $2,1,4,3$。
至少需要 $2$ 次交换，有 $2$ 种方法。

第三组数据：$n=2$，排列为 $1,2$，已经有序，$m=0$，只有 $1$ 种方法（不交换）。

数据范围

• $1 \le n \le 10^5$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB