Advertising ICPC

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

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×22 \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.

입력

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

The next nn lines each contains a string of length mm. 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 nn lines form the grid that represents the flag.

출력

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