걸작

세계적으로 유명한 화가 Theodore Cadman Spencer가 "Magenta Square"와 "Fuchsia Circle"에 이어 다음 걸작을 작업하고 있다. 이번 작품은 단 하나의 기하 도형으로 설명할 수 없다. Theodore가 완성으로 나아가는 여정에서 분명한 도약이다.

거장은 $1 \times 1$ 크기의 정사각형 칸으로 나뉜 $n \times n$ 정사각형 모양의 거대한 캔버스를 쓴다. 캔버스는 처음에 모두 흰색이고, 화가는 붓으로 일부 칸을 maroon으로 칠한다.

그는 붓을 왼쪽 위 모서리(1행 1열)에 놓고 오른쪽 아래 모서리까지 옮긴다. 매 단계마다 오른쪽으로 한 칸 또는 아래로 한 칸 움직인다. 붓이 닿은 칸은 즉시 maroon이 된다. 오른쪽 아래 모서리에 도착하면 왼쪽 또는 위로 움직여 처음 시작한 칸으로 돌아와 끝낸다. 경로는 그가 자유롭게 고른다. 두 번 칠해진 칸은 겉모습이 바뀌지 않는다.

당신은 Spencer의 작품을 좋아하는 팬이자 초보 해커다. 화가의 컴퓨터에 침입해 걸작의 설계도를 내려받으려 했지만 파일이 너무 커서 받을 수 없었다. 그래서 다음과 같이 압축했다. $n$개의 행마다 그 행의 maroon 칸 수를 세고, $n$개의 열마다 같은 방식으로 셌다. 이 $2n$개의 값을 로컬 서버에 저장한 뒤 발각되기 전에 자리를 떴다.

이제 걸작이 만들어지는 정확한 과정을 알고 싶다. 압축된 형태는 관심 없다. 그렇다면 이 정보로 무엇을 알 수 있을까? 얻은 정보와 일치하는 그림을 만드는 붓 경로의 수를 구하라. 어느 순간에든 화가가 다른 방향을 고르면 두 경로는 다르다. 서로 다른 두 경로가 같은 그림을 만들 수 있지만, 과정을 기준으로 하므로 둘 다 따로 센다. 답은 $10^9+7$로 나눈 나머지로 출력한다.

첫 줄에 테스트 케이스 수 $z$ ($1 \le z \le 30$)가 주어진다. 각 테스트 케이스의 첫 줄에는 캔버스 크기 $n$ ($1 \le n \le 100\,000$)이 주어진다. 둘째 줄에는 각 행의 maroon 칸 수 $r_i$ ($0 \le r_i \le n$) $n$개가 주어진다. 다음 줄에는 같은 형식으로 각 열의 값이 주어진다.

각 테스트 케이스마다 주어진 행과 열의 값에 맞는 그림을 만드는 붓 경로의 수를 $10^9+7$로 나눈 나머지로 한 줄에 출력한다.