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
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,
The next
These
Output
Output a single integer, which is the number of ways to fill
the flag such that it is advertising ICPC, modulo
Sample Input 1 | Sample Output 1 |
---|---|
3 3 ??? ?I? ??? |
243 |
Sample Input 2 | Sample Output 2 |
---|---|
2 2 IC PC |
1 |