题目描述

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

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

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

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

例如排列 $\red{2,3,1}$ 至少需要 $\red 2$ 次交换才能变为 $\red{1,2,3}$ 。操作方法共有 $\red 3$ 种，分别是：

方法一：先交换数字 $\red{2,3}$，变成 $\red{3,2,1}$，再交换数字 $\red{3,1}$，变成 $\red{1,2,3}$。

方法二：先交换数字 $\red{2,1}$，变成 $\red{1,3,2}$，再交换数字 $\red{3,2}$，变成 $\red{1,2,3}$。

方法三：先交换数字 $\red{3,1}$，变成 $\red{2,1,3}$，再交换数字 $\red{2,1}$，变成 $\red{1,2,3}$。

输入格式

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

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

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

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

输出格式

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

样例

输入样例

3
3
2 3 1
4
2 1 4 3
2
1 2

输出样例

3
2
1

提示

$\red{1\leq n\leq 10^5}$