Vetrivel is standing at position (i, j) on an n x m grid. There are various mountains on the grid denoted by 'x'. Non-mountainous areas on the grid are denoted by '.'. The position (i, j) on the grid is definitely a non-mountainous area. From a cell at position (i, j) he can move to any of the four adjacent cells, provided the adjacent cell is non-mountainous. He cannot move from a non-mountainous to a mountainous area. From position (i, j), determine the no of unique paths to reach the borders of the grid. Output the result modulo 1e9 + 7.

Note
1. The four borders of the grid are shown in(red) the following figure:

2. An adjacent cell is a cell that shares at least one edge with the current cell.
3. Vetrivel will not jump to any cell, once he reaches any one of the four borders.
4. Two paths are distinct if there is at least one cell (i, j) that is present in one path, but not in the other.

Input
The first line of input contains a number t, the no of test cases(1 <= t <= 100).
The first line of each test case contains four space separated integers, n, m, i and j(1 <= i, j <= n, m <= 8).
The following n lines each contains a string of length of m. Each element of the string is either 'x'(denoting a mountainous area) or '.'(denoting a non-mountainous area).

Output
For each test case, print a line containing the no of ways of reaching one of the four borders of the grid modulo 1e9 + 7.

Example
Input
1
5 5 2 2
xx.xx
xx.xx
.....
xx.xx
xx.xx

Output
4

Explanation
From position (2, 2), you can move either directly upwards, rightwards, leftwards or downwards. Thus there are four paths.
(Look at the image for a better explanation)


Example 2
Input
1
3 3 1 1
...
...
...

Output
4