Description

Youyou is sent to this computer lab to investigate. The lab is an $n \times m$ matrix. Each cell is either O or X, where O means the cell is a seat and X means empty space. Every seat must be occupied by a student, and there is at least one seat.

To identify the cheating students, Youyou must know how many possible valid seating assignments there are in this lab. In ION 2048, contestants come from $k$ schools, and the seating must satisfy:

• The seats in the exam room are composed of several long “strips”, which makes management easier.
• No contestant can sit adjacent to a contestant from the same school, to prevent communication.

Two seats are adjacent if and only if they share a common edge.

A strip is defined as follows: except for the two endpoints which have exactly one adjacent seat, every seat has exactly two adjacent seats. Of course, a single seat also counts as a strip.

For example, the following are “strip-shaped seats”.

The following are not “strip-shaped seats”.

Note: the numbers in the cells indicate the number of adjacent seats.

Compute the total number of valid seating assignments. Since the result may be very large, output it modulo the prime $998244353$. If this lab itself cannot be an ION 2048 exam lab, the answer should be $0$.

Input Format

The first line contains three positive integers $n$, $m$, and $k$.

The next $n$ lines each contain $m$ characters describing the lab. It is guaranteed that only O and X appear, and O appears at least once.

Output Format

Output one integer: the result modulo the prime $998244353$.

2 3 2
OOX
XXO

4

2 3 3
XOX
XOO

12

2 3 4
XOO
XOO

0

Hint

Sample 1 Explanation

There are $4$ possible cases. Red represents students from school $1$, and blue represents students from school $2$:

Sample 2 Explanation

There are $12$ possible cases. Red represents students from school $1$, blue represents students from school $2$, and yellow represents students from school $3$:

Sample 3 Explanation

The lab is not arranged in strips, so the answer is $0$.

Constraints

• Subtask 1 (10 points): $n = 1$, $k = 2$.
• Subtask 2 (15 points): $n = 1$, $2 \le m,k \le 8$.
• Subtask 3 (15 points): $n = 1$.
• Subtask 4 (20 points): it is guaranteed that the seats form strips, $k = 2$.
• Subtask 5 (20 points): it is guaranteed that the seats form strips.
• Subtask 6 (20 points): no special restrictions.

For all testdata, $1 \le n, m \le 10^3$, $2 \le k \le 10^9$.

Translated by ChatGPT 5