Description

小 A 穿越到了古老的数据结构国，这个国家的国树叫做二叉查找树。 数据结构国每年会进行一次神秘的祭祀活动，具体来说就是首先选出 $n$ 位德高望重的国民， 这些国民每人被钦定一个 $1$ 至 $n$ 的编号，不存在两个人有相同的编号；然后这 $n$ 位国民随机站成 一排；接着，国王将会将这 $n$ 位国民以编号为权值，从左向右依次放到（插入）他们的国树—— 二叉查找树上，当然一开始二叉查找树为空。最后我们得到了一棵二叉查找树，称之为 $T$。 数据结构国的祖先们发现，国民排列是一个 $1$ 到 $n$ 的排列，而且随机站成一排的排列对最后 得到的二叉查找树 $T$ 的形态有较大的影响。 假设当前的国民排列为 $Π$，数据结构国的祖先经过了 多次实验，将来年的幸运值定义为满足下列条件的排列个数：

1. 排列与当前的国民排列 $Π$ 不同；
2. 按照该排列，以国民编号为权值，从左向右依次放到（插入）一棵初始为空二叉查找树上， 最终二叉树与 $T$ 完全相同。

数据结构国同时发现，这个幸运值可能很大。但是经过实验他们发现，幸运值并不是越大越好，找规律后发现，幸运值对 $(10^9 + 7)$ 取模后的结果才是真正重要的数据。 显然数据结构国的数据结构与算法并不发达，他们发现一共有 $n!$ 种不同的排列，对这些排列进行统计并且计算来年的幸运值将会是一件困难的事情，于是他们找到了穿越来的小 A。可惜小 A 学艺不精，于是他希望来自未来的你们能够帮他统计一下. 给定当前的国民排列 $Π$，计算来年的幸运值对 $(10^9 + 7)$ 取模后的结果。 小 A 打算在数据结构国居住 $m$ 年，于是你需要回答 $m$$ 个不同的询问。

Format

Input

输入文件第一行，一个数 $m$，表示小 A 在数据结构国居住的年数。 接下来 $m$ 行，每行表示一年的数据。每行第一个数 $n$，表示德高望重的国民数量；接下来 $n$ 个数，表示国民排列 $Π$。

Output

输出文件共 $m$ 行，对于每年的数据输出一行，一个数，表示来年的幸运值对 $(10^9 + 7)$ 取模 后的结果。

Samples

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

1
5
0

见下发文件

见下发文件

样例解释

第一年时，仅有排列 $(2, 3, 1)$ 满足条件； 第二年时，5 个排列 $(3, 1, 2, 4, 5),(3, 1, 4, 2, 5),(3, 1, 4, 5, 2),(3, 4, 1, 2, 5),(3, 4, 1, 5, 2)$ 满足条件； 第三年时，没有排列满足条件。

Limitation

对于 30% 的数据，满足 $1 ≤ n ≤ 10$； 对于 50% 的数据，满足 $1 ≤ n ≤ 10^2$； 对于 100% 的数据，满足 $1 ≤ n ≤ 10^3 , 1 ≤ m ≤ 10^2$。