19514번 - Intersection is Not Allowed! 다국어

문제

Consider a board of $N \times N$ squares. There are $K \le N$ pieces on the board. The pieces are initially placed on some of the top squares of the board.

A piece located at square $(r, c)$ can move either one square to the right to $(r, c + 1)$ or one square down to $(r + 1, c)$.

Your task is to count how many different ways there are to move all pieces to the given positions at the bottom of the board, so that the paths of any two different pieces have no common squares. Two ways are considered different if there exists a piece which has different routes in these ways. As the number of ways can be rather large, find it modulo 10ドル^{9} + 7$.

입력

The first line of input contains an integer $T,ドル the number of test cases (1ドル \le T \le 400$).

Each test case begins with a line containing two integers $N$ and $K$ representing the size of the chessboard and the number of pieces, respectively (1ドル \le N \le 10^5,ドル 1ドル \le K \le 100$).

The second line contains $K$ integers $a_1,ドル $a_2,ドル $\ldots,ドル $a_K$ representing the initial positions of the pieces (1ドル \le a_1 < a_2 < \ldots < a_K \le N$). Formally, the pieces are initially located at squares $(1, a_1),ドル $(1, a_2),ドル $\ldots,ドル $(1, a_K)$.

The third line contains $K$ integers $b_1,ドル $b_2,ドル $\ldots,ドル $b_K$ representing the final positions of the pieces (1ドル \le b_1 < b_2 < \ldots < b_K \le N$). Formally, the pieces should be moved to $(N, b_1),ドル $(N, b_2),ドル $\ldots,ドル $(N, b_K)$.

The sum of all $N$ in the input does not exceed 2ドル \cdot 10^7$.

The sum of all $K$ in the input does not exceed 2ドル \cdot 10^4$.

출력

Print $T$ lines, one for each test case. Each line must contain the number of different ways to move the pieces modulo 10ドル^{9} + 7$.

제한

힌트