Hide

Problem D
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×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 (2n,m8), 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 998244353.

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

Please log in to submit a solution to this problem

Log in