数数数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

将1到N,N个整数进行排列,一共有N!中不同的排列方式。现在问题来了,给出其中的一个序列S,让你计算在N!个序列中有多少个序列的字典序小于S,答案对1000000007取余。

Input

10组输入。
对于每组输入,第一行有两个整数N,Q(1 <= N <= 10000,1 <= Q <= 10)。
接下来的Q行,代表Q次询问,每行N个整数Ai(1 <= Ai <= N)。

Output

对于每次询问输出一个整数代表答案对1000000007取余后的结果。

Sample Input

3 3
1 2 3
2 1 3
3 1 2

Sample Output

0
2
4

Hint

 

Source

zmx