Advertising ICPC

시간 제한1초메모리 제한1024 MB

요약

C, I, P, ?로 채워진 n×m 격자를 C, I, P로 채울 때, IC/PC 모양의 2×2 블록이 적어도 하나 존재하는 경우의 수를 998244353으로 나눈 나머지를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 비트 연산, 조합론
정답자: 아직 제출이 없습니다

문제

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.

입력

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 a single integer, which is the number of ways to fill the flag such that it is advertising ICPC, modulo $998\\,244\\,353$ .

예제2

예제 1
입력
```
3 3
???
?I?
???
```
예상 출력
```
243
```
예제 2
입력
```
2 2
IC
PC
```
예상 출력
```
1
```