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 |
