초콜릿 나눠 팔기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

3×N 초콜릿 덩어리에서 R행 C열 한 칸을 잘라내고 남은 칸을 도미노로 나누는 방법의 수를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

코코는 초콜릿 공장을 운영하고 있다. 이 공장의 기계는 초콜릿을 $3 \times N$ 크기(가로 $N$ , 세로 $3$ )의 직사각형 덩어리로 생산한다. 코코는 이 덩어리를 $\lfloor \frac{3N}{2} \rfloor$ 개의 $1 \times 2$ 또는 $2 \times 1$ 크기의 초콜릿으로 나누어 판매하려고 한다. 어째서인지 $N$ 이 항상 홀수라서, 코코는 $1 \times 1$ 조각을 하나 골라서 잘라 먹고 남은 부분을 나누어 팔기로 했다. $N$ 의 값과 코코가 먹은 조각의 위치( $R$ 행 $C$ 열)가 주어졌을 때, 남은 초콜릿 덩어리를 나누는 방법의 수를 계산해보자.

입력

첫 줄에는 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스마다 $N$ , $R$ , $C$ 의 값이 한 줄에 주어진다.

출력

각 테스트 케이스의 정답을 각 줄에 출력한다. 단, 정답이 매우 클 수 있으므로 정답을 $10^9+7$ 로 나눈 나머지를 출력한다.

제한

$1 \le T \le 10^5$
$1 \le N \le 10^5$ , $N$ 은 홀수
$1 \le R \le 3$ , $1 \le C \le N$

예제1

예제 1
입력
```
3
5 1 1
5 2 2
5 1 2
```
예상 출력
```
15
8
0
```