Masterpiece

The world-renowned artist Theodore Cadman Spencer is working on his next masterpiece, following the ingenious "Magenta Square" and the unconventional "Fuchsia Circle". This time the work cannot be described as a single geometric shape. It is a clear step forward in Theodore's journey toward completion.

The maestro uses a huge canvas shaped like an $n \times n$ square, divided into $1 \times 1$ squares. The canvas starts entirely white, and the artist paints some of the squares maroon with his brush.

He places the brush in the upper-left corner (first row, first column) and slides it to the lower-right corner. At each step he moves either one square to the right or one square down. Every square the brush touches turns maroon immediately. When he reaches the lower-right corner, he goes back, moving either left or up, until he finishes on the square where he started. He chooses his path freely. Squares painted twice keep the same look.

You are a fan of Spencer's work and a novice hacker. You broke into the artist's computer and tried to download the plans for the masterpiece, but the file was too large. So you compressed it as follows. For each of the $n$ rows, you counted the maroon squares in that row. You did the same for each of the $n$ columns. You saved these $2n$ values to your local server and left before getting caught.

You want to know the exact process that creates the masterpiece. The compressed form does not matter to you, but how much does it tell you? Count the distinct brush paths that produce a painting consistent with the information you have. Two paths differ if at some moment the artist picks a different direction. Two different paths can produce the same painting, and both are counted because you care about the process. Print the count modulo $10^9+7$.

The first line contains the number of test cases $z$ ($1 \le z \le 30$). Each test case starts with a line containing the canvas size $n$ ($1 \le n \le 100\,000$). The second line contains $n$ integers $r_i$ ($0 \le r_i \le n$), the number of maroon squares in each row. The next line gives the column counts in the same format.

For each test case, print one integer: the number of brush paths whose painting matches the given row and column counts, modulo $10^9+7$.