Time limit: 1s
Memory limit: 256MB
There is a chess board of rows and columns.
There are cells that are occupied by chess pieces, and all other cells are empty.
You don't know what exact pieces occupy them, but you know that each piece is either a rook or a bishop.
You also know that no rook attacks a bishop, and no bishop attacks a rook.
How many valid arrangements of pieces exist? Since this number might be too big, output it modulo .
Two arrangements are considered different if there is at least one cell which is occupied by a different piece.
The input consists of:
- a line containing integers , , .
- lines, the -th of which consisting of integers , , which mean that the cell at the -th row and -th column is occupied.
The output must contain a single line consisting of integer , the number of piece arrangements modulo , such that no rook attacks a bishop and no bishop attacks a rook.
Constraints and clarifications
- , for each
- Each cell is occupied by at most one piece (in other words, either or for ).
|5||51||No additional constraints|
4 2 2 1 1 3 2
3 3 3 2 1 3 3 1 1