#443 Unusual Permutation

Loading problem...

Preparing the statement, recent submissions, and submit form.

Statement

$1$ 부터 $N$ 까지의 정수를 각각 한 번씩 사용한 순열 $A$ 를 생각하자. 다음 조건을 만족하는 순열의 개수를 구하여라.

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

정답을 $1\,000\,000\,007$ 로 나눈 나머지를 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ case $_1$ case $_2$ $\vdots$ case $_T$

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

$N\ l\ r\ k$

각 테스트 케이스마다 조건을 만족하는 순열의 개수를 $1\,000\,000\,007$ 로 나눈 나머지를 한 줄에 출력한다.

#	Score	Constraints
1	15	$N \leq 8$ 이고, 모든 테스트 케이스에 대한 $N$ 의 합은 $8$ 이하이다.
2	15	$l=r$ 이다.
3	25	$N \leq 2\,000$ 이고, 모든 테스트 케이스에 대한 $N$ 의 합은 $2\,000$ 이하이다.
4	45	추가적인 제약이 없다.

Input

2
3 1 2 2
5 2 5 3

Output

2
0