The Light King and the Mirror Maze 2

No attempts yetTime limit2sMemory limit256 MB

Problem

The young light king likes toys. His current favorite is an N×MN \times M rectangular board where a diagonal mirror can be pushed into or pulled out of every cell. Once the mirrors are in place he aims a laser at the center of a border cell, perpendicular to that cell's outer edge, and the beam leaves the board through another cell. He never tires of watching it.

Every border cell carries one natural number, assigned this way.

  • the MM cells along the top: 11 to MM, left to right
  • the NN cells along the left: M+1M+1 to M+NM+N, top to bottom
  • the NN cells along the right: M+N+1M+N+1 to M+N+NM+N+N, top to bottom
  • the MM cells along the bottom: M+N+N+1M+N+N+1 to M+N+N+MM+N+N+M, left to right

Each of the four corner cells gets two numbers. A beam entering through the top edge and a beam entering through the left edge use different numbers. For N=2N = 2 and M=3M = 3 the border is numbered like this.

      1   2   3
  4   .   .   .   6
  5   .   .   .   7
      8   9  10

The king cares about toys where a laser fired into xx comes out at yy. He also wants a particular arrangement, so the mirror layout he asks for is given as NN strings of length MM. The characters mean this.

  • /: a mirror that sends a beam arriving from the left upward, a beam from above to the left, a beam from the right downward, and a beam from below to the right.
  • \: a mirror that sends a beam arriving from the left downward, a beam from above to the right, a beam from the right upward, and a beam from below to the left.
  • .: an empty cell, where the beam passes straight through.
  • ?: a cell that may hold any one of the three above.

The more ? characters there are, the more layouts the board admits. Count the layouts in which a laser fired into xx leaves at yy.

Input

The first line has two integers NN and MM (1N,M81 \le N, M \le 8), the size of the board, and two integers xx and yy (1x,y2(N+M)1 \le x, y \le 2(N+M)), separated by spaces.

Each of the next NN lines has a string of length MM. The string consists only of /, \, . and ?.

Output

Print the number of layouts in which a laser fired into xx leaves at yy, taken modulo 1000710007.

Hint

One cell with a mirror in it pairs up its four edges. . pairs top with bottom and left with right, / pairs top with left and bottom with right, and \ pairs top with right and bottom with left. Across the whole board the edges join into paths that always match border numbers in twos, so the answer is 00 when xx equals yy.