Hide

Problem J
Advertising ICPC

You’re making a flag to try to advertise ICPC! The flag takes the form of a grid that is already filled with some “C”, “I”, and “P” letters. A flag is advertising ICPC if there exists at least one $2 \times 2$ subgrid that looks exactly like the following:

   IC
   PC

The flag cannot be rotated or reflected. Every square in the grid must be filled with either a “C”, “I”, or “P”. Count the number of ways to fill the unfilled locations on the flag such that the flag is advertising ICPC.

Input

The first line contains two integers, $n$ and $m$ $(2 \le n, m \le 8)$, where $n$ is the number of rows and $m$ is the number of columns in the grid.

The next $n$ lines each contains a string of length $m$. Each character in the string is either a “C”, “I”, “P”, or “?”. A “?” means that that location is not yet filled with a letter.

These $n$ lines form the grid that represents the flag.

Output

Output a single integer, which is the number of ways to fill the flag such that it is advertising ICPC, modulo $998\, 244\, 353$.

Sample Input 1 Sample Output 1
3 3
???
?I?
???
243
Sample Input 2 Sample Output 2
2 2
IC
PC
1

Please log in to submit a solution to this problem

Log in