Problem Background

ION 2048 has concluded, but ℲƆƆ has discovered a severe cheating incident in one of the computer labs.

Problem Description

Youyou has been tasked with investigating this computer lab. The lab is represented as an $n \times m$ matrix, where each position is either O or X. O indicates a seat, and X indicates an empty space. Each seat must be occupied by a student, and there is at least one seat.

To identify the cheating students, Youyou needs to determine the number of possible seating arrangements in the lab. ION 2048 has participants from $k$ schools, and the seating must meet the following requirements:

• The seats in the exam room are arranged in several rectangular strips for easier management.
• No student can be seated adjacent to another student from the same school to prevent communication.

Two seats are considered adjacent if they share a common edge.

A strip is defined as having exactly two adjacent seats for each seat, except for the two endpoints which have only one adjacent seat. A single seat also qualifies as a strip.

For example, the following are valid "strip seating" arrangements:

The following are not valid "strip seating" arrangements:

Note: The numbers in the grid indicate the number of adjacent seats.

Calculate the total number of valid seating arrangements, and output the result modulo the prime number $998244353$. If the lab cannot possibly be a valid ION 2048 exam room, 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, representing the layout of the lab. Only O and X characters are allowed, and there is at least one O.

Output Format

Output a single integer, the result modulo $998244353$.

Sample Input and Output

Sample Input #1

2 3 2
OOX
XXO

Sample Output #1

4

Sample Input #2

2 3 3
XOX
XOO

Sample Output #2

12

Sample Input #3

2 3 4
XOO
XOO

Sample Output #3

0

Notes

Sample 1 Explanation

There are 4 possible arrangements, with red representing students from school 1 and blue representing students from school 2:

Sample 2 Explanation

There are 12 possible arrangements, with red representing students from school 1, blue representing students from school 2, and yellow representing students from school 3:

Sample 3 Explanation

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

Data Range and 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): The seating arrangement is guaranteed to be in strips, $k = 2$;
• Subtask 5 (20 points): The seating arrangement is guaranteed to be in strips;
• Subtask 6 (20 points): No special restrictions.

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

见题面 Input 部分

见题面 Output 部分