#443 Unusual Permutation

Loading problem...

Preparing the statement, recent submissions, and submit form.

#443 Unusual Permutation | DOJ

Statement

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$ $\vdots$ case $_T$

Each test case is given in the following format:

$N\ l\ r\ k$

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$ .
3	25	$N \leq 2\,000$ , and the sum of $N$ over all test cases does not exceed $2\,000$ .
4	45	No additional constraints.

Input

2
3 1 2 2
5 2 5 3

Output

2
0