Drawing Lines on Grid

You are given an \(n \times m\) grid. Some cells are marked as bad and cannot be passed through when drawing a line. A drawing consists of drawing zero or more lines according to the following rules:

• Each line drawing starts at the center of a cell that has not been drawn on before.
• In one move, you can extend the line in one of the four cardinal directions (up, down, left, right) to a neighboring cell (the target cell).
• The target cell can be drawn onto if and only if one of the following conditions holds:
  1. If the target cell has not been drawn on before, you can draw a straight line from the current cell to the target cell (passing through the midpoint of the common edge). After drawing, you may choose to either end the current line or continue.
  2. If the target cell has already been drawn on and that drawn line is a full-line (i.e. a line that goes straight through the entire cell in either the vertical or horizontal direction without a change in direction), then you can draw another full-line in the target cell but it must be perpendicular to the already drawn line.
  3. If the target cell is the starting cell of the current drawing, then you can draw a line back to it (again passing through the midpoint of the common edge). In this case you must end the current drawing.
• You cannot draw outside the grid and you cannot pass through any bad cell in any drawing.
• You have c different colors available, and for each drawn line you may choose any color.

Finally, the total number of essentially different drawings is defined as follows:

• If \(op = 0\): two drawings are considered the same if, after ignoring the cells that are bad, they have the exact same pattern (i.e. the same line directions and colors in every cell).
• If \(op = 1\): two drawings are considered the same if, after ignoring the bad cells, they are either identical or one becomes identical to the other after a rotation of \(180^\circ\).

Since the answer might be very large, output the answer modulo \(998244353\).

Note: For the purpose of this problem, the input cases have been chosen such that no valid drawing moves are possible. In all cases, the only possibility is to draw nothing, which counts as one drawing.

inputFormat

The input is given as follows:

 n m c op
 grid_line_1
 grid_line_2
 ...
 grid_line_n

Here, n and m are the dimensions of the grid. c is the number of available colors, and op is either 0 or 1, indicating the equivalence criteria described above. Each of the next n lines contains a string of length m consisting of characters: a dot (.) indicates a good cell, while a hash (#) indicates a bad cell.

outputFormat

Output a single integer, the number of essentially different drawings modulo \(998244353\).

sample

1 1 3 0
.

1