Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bad Neighbors 2

By TarifEzaz · Limits 1s, 512 MB

As some of you already know, Nocu City has a history of having bad neighbors. These bad ones, take away free lands whenever they find them. These unlawful activities has made the entire city inhospitable. After bad neighbors have conquered all the free spaces of Nocu city, a new law was prepared and passed by the government. As a result, all the places that were conquered illegally are rescued. In order to stop this anarchy from occurring again, the government have placed some patrols in some of the free spaces of the land.

For simplicity, let’s assume that the blocks of Nocu City are integer points over a straight line. The leftmost block of the neighborhood is labeled with 1, and the rightmost block is labeled with N ( 1 <= N <= 100000 ). 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 at the same block.

A bad neighbor can choose an empty slot to his right or to his left and acquire it. But he might only do so in some direction when the first non-empty block in that direction is not occupied by a patrol. For example, we have N = 7, three neighbors are placed in slots { 1, 3, 6 } and the evil neighbor is located at position 3. Then he can only conquer position 2, if the neighbor placed at position 1 is not a patrol. Similarly, he can also conquer position 4 and 5 if the neighbor placed at position 6 is not a patrol. Note that, he will not be able to conquer position 7, since in that case he would have to go through an occupied land.

A patrol can guard every empty slots to this right or to his left until he encounters an occupied slot. But the government have limited resources and they can not assign enough patrols to guard the entire area. Good neighbors are the ordinary ones, they do not acquire any empty slots, and do not stop the neighboring bad inhabitants from acquiring empty slots either.

Now, tell us that in how many ways the acquirable empty slots will be occupied by the bad neighbors. Two ways are different if the same slot is occupied at a different time, or by different bad neighbors. In one configuration, an empty slot may only be occupied by one bad neighbor. You can assume that the empty slots can be occupied sequentially. It means that no two slots can be occupied at the same time. Please see the sample for further clarification. Also, notice that some of the empty slots may never be occupied.

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 ( 0 <= M <= N ), where M denotes the number of neighbors currently available in the city. In the following line there will be M integers contain the location pi ( 1 <= pi <= N ) of the houses of each neighbor i. The locations will be given in increasing order. In the next line again there will be M integers u1 , u2 , … uM (0 <= ui <= 2), where the i’th integer describes the type of the i'th neighbor. The i’th integer is 0, if it is a humble neighbor, 1 if is a bad neighbor and 2 if it is a patrol. Each testcase will contain 0 or more neighbors of each type.

Output

For each case, print the result, the number of ways that blocks can be conquered. Since the answer can be very big, print the remainder of the answer when divided by 1000000007. Each answer should be printed on a separate line.

Samples

InputOutput
1
4 2
1 4
1 1
4
InputOutput
1
7 3
1 4 6
0 1 2
1

In the first sample, there are two empty slots { 2 , 3 }, these can be occupied in the following manner:

Bad neighbor at position 1 gets both slots 2 and 3.

Bad neighbor at position 4 gets both slots 3 and 2.

Bad neighbor at position 1 gets slot 2 and then bad neighbor at position 4 gets slot 3.

Bad neighbor at position 4 gets slot 3 and then bad neighbor at position 1 gets slot 2.

In the second sample, the empty slots are { 2 , 3, 5 , 7 }. But the two acquirable empty slots 2 and 3 can only be owned by the bad neighbor at position 4.

Discussion

Statistics


86% Solution Ratio

shakil_ruetEarliest, Dec '16

Double_OFastest, 0.1s

oneoff.WcljHi2ZI8Lightest, 1.7 MB

Ultra.NazmulShortest, 1506B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.