Bits with Signature

Let's consider a sequence consisting of binary digits (bits). For the purposes of this exercise, we will calculate the signature of this sequence by counting the number of consecutive "1" digits (ones) it contains. For example, consider the sequence:

In this sequence, we first encounter three ~(3)~ consecutive ones, then two ~(2)~ more, followed by four ~(4)~, and finally one ~(1)~ more. Therefore, the signature of this sequence consists of four numbers: ~3,\ 2,\ 4,\ 1~. To find the signature of a sequence, we skip over the zeros (which only act as separators) and count the number of consecutive ones encountered.

Note that the sequence below has the exact same signature:

You are given a sequence consisting of ~N~ binary digits, some of which are erased, indicated by a dot in their place. For example:

You are also given a desired signature, for example, ~3,\ 2,\ 4,\ 1~.

In how many different ways can you fill in the erased digits with binary digits so that the resulting sequence has the given signature?

Problem

Develop a program in one of the following languages: PASCAL, C, C++, JAVA, which reads ~T~ queries of the above format. For each query, you will be given a sequence of binary digits, some of which will be erased, along with a desired signature. For each query, your program should print the number of ways the erased digits can be filled in so that the resulting sequence has the desired signature.

For your submissions to DMOJ, use STDIN and STDOUT. The format of input and output should be as described below.

Input:

The input file named bitsign.in is a text file with the following structure. The first line contains an integer ~T~, the number of queries to follow. Then, the ~T~ queries follow, each described by three lines of input. The first of these lines contains two integers ~N~ and ~M~, separated by a single space: the number of digits in the sequence and the number of elements in the signature. The second line contains a string of ~N~ characters, each of which can be "0", "1", or "." (dot). The third line contains ~M~ positive integers, separated in pairs by a single space, representing the desired signature.

Output:

The output file named bitsign.out is a text file with the following structure. It should contain ~T~ lines, one line for each query, in order. Each line should contain an integer, the answer to the corresponding query. Since the answers can generally be large numbers, print their remainder when divided by the number ~1.000.000.007~ (modulo).

Example of Input - Output Files:

input:

5
7 3
...0111
1 1 3
14 3
0..00..000.110
1 1 3
15 4
.1.1.1.1.1.1.1.
1 3 1 6
13 3
.0..0.0001000
4 1 1
12 3
.111........
3 2 1

output:

1
4
1
0
10

Explanation: We have ~T=5~ queries.

In the first query, we can complete the sequence in only one way so that the desired signature is obtained: 1010111

However, in the second query, for the same signature, we can complete the sequence in four different ways: 01000100001110, 01000010001110, 00100100001110, and 001000100011110

In the third query, there is again only one way to complete the sequence to obtain the desired signature: 010111010111111

In the fourth query, there is no way to obtain the desired signature, as four consecutive "1"s cannot be formed.

In the last query, the answer is ~10~.

Constraints

• ~1 \leq T \leq 10~
• ~1 \leq N \leq 2000~ and ~1 \leq M \leq 1000~
• The sum of the lengths of the sequences for all queries will not exceed ~3000~.
• For test cases with a total value of ~20\%~, it will be ~N \leq 15~.
• For test cases with a total value of ~30\%~, the number of deleted digits in each sequence will not exceed ~15~.
• For test cases with a total value of ~50\%~, it will be ~N \leq 100~.
• In the output, all lines must terminate with a newline character.
• Time Limit: ~1~ sec.
• Maximum Available Memory: ~256~ MB.

Note: Make sure to read the input and print the output efficiently, especially if you are coding in C++ or Java.