问题 G: Casino Royale

In Casino Royale, one of the famous games is played on a decimal string s1s2…sn, where si∈ {'$\text{1}$', '$\text{2}$'}. The two players move in turns, the first player moves first. In each move, the current player selects either the first bit or the last bit of the string, adds it to this player's score, and removes it from the string. The game ends when the string is empty. Both players want to maximize their scores, the one with the maximum score wins.

Before the first move of a game, the observers can see a portion of bits in the string, then make a bet on who will win in the end. Little Q is the owner of the Casino Royale. He is interested in how to predict the result of the above game such that he can earn a lot of money by predicting.

You will be given the initial string with some bits hidden. Little Q will then give you $q$ queries. In each query, you will be given two integers $A$ and $B$, denoting the final scores of the first player and the second player respectively, you need to report the number of distinct initial strings that will lead to this result if both players play optimally.

The first line contains a single integer $T$ ($\le T\le 100$), the number of test cases. For each test case:

The first line contains two integers $n$ and $q$ ($1\le n\le 50$, $1\le q\le (2n+1)(2n+1)$), denoting the length of the initial string and the number of queries.

The second line contains a string $s$ of length $n$ (si∈ {'1', '2', '$\text{?}$'}), denoting the initial string that can be seen by the observers. Here '$\text{?}$' denotes the value of the corresponding bit is hidden.

Each of the following $q$ lines contains two integers $A$ and $B$ ($0\le A,B\le 2n$), denoting a query.

2
3 2
121
2 2
1 3
2 4
??
1 1
2 2
2 1
1 2

1
0
1
1
2
0