After the ingenious "Magenta Square", and the unconventional "Fuchsia Circle", the world-renowned artist Theodore Cadman Spencer is working on his next masterpiece. This time the great master has really outdone himself, as this work of art will be indescribable in terms of a single geometric shape, which is clearly a leap forward in Theodore's journey to completion.

The maestro has decided to use a huge canvas shaped like an n-by-n square, perfectly divided into 1-by-1 squares. The cloth starts entirely white, and the artist will use his brush to paint some of the squares maroon.

Theodore's idea is to place his paintbrush in the upper-left corner of the canvas (i.e. in the first row and the first column), and gently slide it to the lower-right corner, always moving either one square to the right, or one square down. All squares touched by the brush will immediately turn maroon. But, as unbelievable as it is, this is not the end of the genius painter's plan! As soon as he gets to the lower-right corner he goes back, moving either left or up, to finally finish in the square where he started. He is free to choose his path as he pleases, and fields that get painted twice don't change the way they look in the slightest.

You are a passionate fan of Spencer's work, and a novice hacker - unable to resist the urge you broke into the artist's computer, and tried to download the plans for his masterpiece. However, the enormous size of the file made it impossible, so you quickly compressed it in the following way. For each of the n rows, you computed the number of maroon squares in that row, then you did the same thing for each of the n columns. Finally, you saved those values onto your local server, and took off before getting caught.

Now, you are unsatisfied - you'd like to know the exact process that will lead to the creation of the masterpiece, and you couldn't care less about the compressed form you got. But how much does it tell you anyway? Compute the number of the distinct paths for the paintbrush that are consistent with the information you have. Two paths are considered different if, at some moment, the artist chooses a different direction. Note that two distinct paths can potentially lead to the same painting, but you care about the process so much that you consider them as different.

As the answer might turn out to be large, output it modulo 109 + 7.

Input

The first line contains the number of test cases z (1 ≤ z ≤ 30). The descriptions of the test cases follow.

The first line of every test case contains the size of the canvas n (1 ≤ n ≤ 100 000). The second line of every test case contains n integers ri (0 ≤ ri ≤ n), the numbers of maroon squares in each row of the painting. In the next line, the descriptions of columns follows, in the same format.

Output

For each test case output one integer: the number of paths that result in a painting consistent with the given information modulo 109 + 7.