Problem Background

Little Pink Rabbit has recently become obsessed with a game called "Tetris."

However, this problem has little to do with Tetris except for both involving grids and colors.

Problem Description

There is a grid graph of size $n \times m$, and Little Pink Rabbit plans to draw lines within it.

He can draw lines multiple times or not at all. Each time he draws a line, it must start from the center of a grid cell that has not been drawn on before.

He can only draw lines in the four cardinal directions (up, down, left, right), with the corresponding grid cell in that direction being the target cell.

A target cell can be drawn on if and only if one of the following three conditions is met:

1. If the target cell has not been drawn on, the line can be drawn to the center of the target cell through the midpoint of the common edge of the two cells, and may choose to end the line here.
2. If the target cell has been drawn on and the line is a line that spans the entire cell, another line can be drawn that is perpendicular to this line and also spans the entire cell. A line that spans the entire cell is defined as a line that does not change direction within the cell, either vertically or horizontally.
3. If the target cell is the starting cell of the current line, the line can be drawn back to the center of the target cell through the midpoint of the common edge of the two cells, and must end the line here.

Of course, the line cannot be drawn outside the grid graph.

Despite the strict rules Little Pink Rabbit has set, he still has many colored pens, and each time he draws a line, he can choose any one of $c$ colors.

Unfortunately, some positions in the grid graph are damaged and cannot be passed through, meaning they cannot be drawn on during any line drawing.

Little Pink Rabbit wants to know, under these restrictions, how many fundamentally different graphs can be drawn?

Little Pink Rabbit does not ask for much. When $\mathrm{op}=0$, two graphs are considered fundamentally the same if, disregarding the damaged cells, they look the same (with the same line directions and colors at each position).

When $\mathrm{op}=1$, two graphs are considered fundamentally the same if, disregarding the damaged cells, they look the same or if they look the same after a $180^\circ$ rotation.

Since the answer could be very large, Little Pink Rabbit only wants to know the result modulo $998244353$.

Input Format

The first line contains three positive integers $n, m, c$ and a number $\mathrm{op}$ that is either $0$ or $1$.

The next $n$ lines, each containing a string of length $m$ consisting of only . and # characters, describe the grid graph. If the $j$-th character in the $i$-th line is #, it indicates that the cell in the $i$-th row and $j$-th column of the grid graph is damaged; otherwise, it is not damaged.

Output Format

Output a single number, which is the answer modulo $998244353$.

Sample Input and Output

Input Sample #1

1 3 2 0
...

Output Sample #1

7

Input Sample #2

1 3 2 1
...

Output Sample #2

5

Input Sample #3

2 2 1 0
..
..

Output Sample #3

16

Input Sample #4

2 2 1 1
..
..

Output Sample #4

10

Input Sample #5

2 2 1 0
..
#.

Output Sample #5

4

Input Sample #6

4 5 1 0
.....
.#.#.
....#
.#...

Output Sample #6

65856

Input Sample #7

4 5 1 1
.....
.#.#.
....#
.#...

Output Sample #7

65616

Notes

Sample 1 Explanation

There are 7 fundamentally different graphs:

Sample 6 Explanation

Below are two fundamentally different graphs:

Data Constraints

This problem uses bundled testing:

• Subtask 1 (12 points): $n=1$, $\mathrm{op}=0$, no damaged cells.
• Subtask 2 (13 points): $c=1$, $\mathrm{op}=0$.
• Subtask 3 (12 points): $c=1$, $\mathrm{op}=1$.
• Subtask 4 (14 points): $m\le 5$, $\mathrm{op}=0$.
• Subtask 5 (25 points): $\mathrm{op}=0$.
• Subtask 6 (8 points): $n\bmod 2=0$, $\mathrm{op}=1$.
• Subtask 7 (8 points): $n\bmod 2=1$, $m\bmod 2=0$, $\mathrm{op}=1$.
• Subtask 8 (8 points): $n\bmod 2=1$, $m\bmod 2=1$, $\mathrm{op}=1$.

For 100% of the data, $1\le n,m\le 9$, $1\le c\le 10^6$, $\mathrm{op}\in\{0,1\}$.

见题面 Input 部分

见题面 Output 部分