In this problem you will have to solve a puzzle game named "Pipeline". 90's kids knows this game very well.
In this game on each level there is an underground Grid with r rows and c columns. There is a source cell (x1, y1) and a destination cell (x2, y2) in the grid.
Now you will be given n pipes. These pipes can be of two types, 1- straight pipe and 2- angled pipe. These pipes can be rotated at 90 degree any number of times.
You will have to connect these pipes Sequentially one after another, starting from the Source to the destination.
You can use pipes p1,p2,....pi where (1 ≤ i ≤ n). If source and destination are already connected then It is considered solved, even without using any pipes.
Each cell can contain only one pipe.
As this game is too easy, the developer made some changes in the game. On each level you will have to answer how many ways are there to solve this puzzle.
For the example above the grid size is (6, 6), source (1, 2), destination(4, 3) and Given 7 pipes: 2, 1, 1, 1, 2, 2, 2.
With these pipes you can solve this puzzle in this 2 ways that are given above.
Input
In the first line you will be given T (1 ≤ T ≤ 100) - the number of levels you will have to play.
On each level :
- The first line will contain r, c, n (1 < r, c ≤ 10) (0 < n ≤ 20) - grid size(r,c) and number of pipes(n).
- The second line will contain n space separated integers p[1,2,...n] - the type( 1 or 2) of the pipe.
- The third line will contain x1, y1, x2, y2 - the source and the destination. Source and Destination cannot be the same cell.
Output
For each level, output the number of ways you can solve this level on each line.
Sample
| Input | Output |
|---|---|
2 5 5 7 2 1 1 1 2 2 2 1 2 4 3 3 3 4 2 2 1 2 2 2 2 3 | 2 5 |
Pipes don't need to enter into the destination cell, It just needs to reach it. You can not place any pipe in the destination cell.
