Bad Neighbors

In the strange neighborhood of Nocu, a lot of people lives pretty happily, or so they think. Like most of the places in Dhaka, Nocu is quite congested. On top of that, many new people arrives once every four months and contributes to the existing society. Some of the neighbors of Nocu, despite their friendly behavior, are evil in their acts. They try to take away all the empty blocks of the city one by one.

For simplicity, let's assume that all the houses of this neighborhood are placed on a straight line. The leftmost block of the neighborhood is labeled with 1, and the rightmost block is labeled with N ( <= 1000 ). Each neighbor has already chosen a block for themselves and created a house there. Since the neighbors are not that friendly, no two neighbors have created a house in the same block.

Initially, some of the blocks may be empty, but if an evil neighbor encounters an empty block to his left or right, he might snatch the land before another evil neighbor does. For example, if we have N = 6, three neighbors locating at blocks { 1, 3, 6 }, and the evil neighbor is located at position 3, then eventually, he will conquer blocks 2, 4 and 5. Now, an evil neighbor can extend his area one block at a time. He can either take the free block to his immediate left or to his immediate right of his currently conquered area. So, in this example, the bad neighbor at location 3 can conquer the areas in each of the following orders: 245, 425, 452. Also note that no evil person can conquer a place which has already been taken.

You have the initial position of the neighbors, and the information of the notoriety of the neighbors. You have to determine, in how many different permutations the empty blocks can be occupied. You can safely assume that for two neighboring person, at least one of them is evil. Also, the first and last neighbors are always evil as well.

Input

The first line of the input contains T ( 1 <= T <= 3 ), the number of testcases. Each case starts with two integers N and M, where M denotes the number of neighbors currently available in the city. The following M integers contain the location pi ( 1 <= pi <= N ) of the houses of each neighbor i. The locations will be given in increasing order. The next M integers will either be 0 or 1, where the i'th integer indicates the notoriety of the i'th neighbor. Here, 1 indicates a humble neighbor and 0 means a naughty one.

Output

For each case, print the result, the number of possible ways that blocks can be conquered. Since the answer can be very large, print the remainder of the answer when divided by 1000000007.

Samples

1
6 3
1 3 6
0 1 0

3

1
4 2
1 3
0 0

2

In the second sample, empty plots can be occupied in two different permutations, (2,4) and (4,2).