#443 Unusual Permutation

Statement

Statement language

Consider a permutation $A$ containing each integer from $1$ to $N$ exactly once. Count the permutations satisfying

\max(A_l,A_{l+1},\cdots,A_r)=k.

Print the answer modulo $1\,000\,000\,007$ .

The input is given in the following format:

$T$ case $_1$ case $_2$

For each test case, print the number of valid permutations modulo $1\,000\,000\,007$ on one line.

#	Score	Constraints
1	15	$N \leq 8$ , and the sum of $N$ over all test cases does not exceed $8$ .
2	15	$l=r$ .

Input

2
3 1 2 2
5 2 5 3

Output

2
0