问题描述
Tina Town 的镇中有一块表面平整光滑的大石头, 当人面向它走进时, 石头的表面就会亮起, 显示出它的用途. 这块石头是前人留下来的东西,是Tina Town算力和控制系统的核心, 同时它也可以显示Tina Town的大小事和行人关注的内容,也可以作为公共的计算机使用 ,极大地方便了人们的生活(特别是上街忘带终端的人们啦).
Tina和Town在这块大石头上玩一个游戏. 石头上首先显示出了1到n排列的n个数,Town则随机交换了一些数, 然后Town通过宏将这个交换的过程记录下来了. Town 问 Tina: 你知道执行几次这个宏, 这些数会恢复最早的排列嘛? Tina是一个蠢蠢的女孩子, 当然不知道啦, 于是她想向你请教呢.
由于答案可能很大,你只需要输出答案对于$3*2^{30}+1=3221225473$(一个素数)的模就行了.
输入描述
第一行一个数$T$,表示数据组数.$T\le 5$
接下来一组数据两行,第一行一个整数$n$,表示排列的长度.$n\le 3\times 10^6$
第二行一个$n$个数表示一个排列$A_1... A_n$,保证数字两两不同且对于所有的$A_i$都有$1\le A_i\le n$.
输出描述
对于每组数据输出一行一个数$ans$,表示答案.
输入样例
2
3
1 3 2
6
2 3 4 5 6 1
输出样例
2
6
Hint
数据规模较大建议使用读入优化.
