Particle Experiment

Albert studies small particles. Each particle has either a positive (+) or a negative (-) charge, and a lab apparatus can flip these charges. The apparatus is a grid of size $R \times C$ that stands upright. Albert fires one particle from the top of each column, at row 1, and a sensor below row $R$ detects it.

For example, in the figure below, $R = 3$, $C = 4$, and the string $S$ = +-++ means that particles are fired from columns 1 to 4 in the order positive, negative, positive, positive. Each particle travels in a straight line through all $R$ cells, from row 1 to row $R$, and reaches the sensor at the bottom.

Some $1 \times 1$ cells of the apparatus have preinstalled switches. A particle that passes through such a cell changes from positive to negative or from negative to positive. Let $K$ be the number of preinstalled switches, and let $X_i$ and $Y_i$ be the row and column index of the $i$-th switch.

In the figure below, $K = 3$, $X = [1, 1, 2]$, and $Y = [2, 4, 4]$. Every detected particle is positive. The particle in column 2 changes from negative to positive. The particle in column 4 changes to negative and then back to positive.

Albert also has many $1 \times 2$ switches, which cover two horizontally adjacent cells. He wants every particle to be positive when it reaches the sensor. Each switch must always cover two cells side by side, and no cell may be covered by more than one switch. For the example above, there are three ways to reach the goal:

• Place switches at row 2, columns 1-2, and at row 3, columns 1-2.
• Place switches at row 2, columns 2-3, and at row 3, columns 2-3.
• Add no switches.

In this example, the two switches are labeled AA and BB for convenience. All switches look identical, so they cannot be told apart.

Another example is $R = 2$, $C = 4$, $K = 0$. Albert has five different ways to reach the goal.

Given $R$, $C$, $K$, $X$, and $Y$, count the ways to add $1 \times 2$ switches to the apparatus so that every particle is positive when it reaches the sensor. The answer can be very large, so print it modulo $10^9 + 7$.

The first line contains the number of test cases $T$.

The first line of each test case contains $R$, $C$, and $K$, separated by spaces. The second line contains a string $S$ of length $C$, which gives the charge of the particle fired from each column at the start. The next $K$ lines each contain $X_i$ and $Y_i$, separated by a space.

Print the answer for each test case on its own line.

• $1 \le T \le 5$
• $1 \le R \le 500$
• $1 \le C \le 10$
• $0 \le K \le \min(R \times C, 1000)$
• For every $i$ with $1 \le i \le K$, $1 \le X_i \le R$ and $1 \le Y_i \le C$.
• Each pair $(X_i, Y_i)$ is unique within a test case, so no cell is given more than once.
• Assume Albert has enough switches to use as many as he needs.