Non‐attacking Chess Piece Placements

You are given an \(n \times m\) chessboard and a special chess piece. This chess piece has an attack pattern defined by a template: a \(3 \times p\) matrix in which each cell is either 0 or 1. The piece is considered to be placed at the cell corresponding to the second row (row index 1) and column \(k\) of the template (note that the indices start from 0). The template tells you the relative positions the piece can attack: if the cell \((r, c)\) in the template has a value 1 then a piece (when placed on the board) will attack the cell located at \(\big(i+(r-1),\; j+(c-k)\big)\) on the board. In particular, since the cell \((1, k)\) is guaranteed to be 1, a piece always "attacks" the cell it occupies.

Your task is to count the number of ways to place any number of these pieces (possibly none) on the \(n \times m\) board such that no two pieces attack each other. Two pieces placed in cells \((i, j)\) and \((i', j')\) conflict if either one attacks the other. More formally, if we define the set of attack offsets as \[ S = \{ (r-1, c-k) \;:\; 0\le r<3, \;0\le c

Because the answer can be huge, output it modulo \(2^{32}\) (i.e. the remainder after division by \(2^{32}\)).

Input Format: The first line contains four integers \(n,\, m,\, p,\, k\). Then 3 lines follow, each containing \(p\) integers (0 or 1), which represent the attack pattern template of the piece.

Output Format: Output a single integer, the number of valid placements modulo \(2^{32}\).

inputFormat

The input begins with a line containing four integers \(n, m, p, k\) (board dimensions, template width, and the column index in the template that represents the piece’s position). Then follow 3 lines, each containing \(p\) integers (either 0 or 1) representing the attack pattern template. It is guaranteed that the cell in the second row (row index 1) and column \(k\) of the template is 1.

outputFormat

Output a single integer: the number of ways to place pieces on the board such that no two attack each other, modulo \(2^{32}\).

sample

1 3 3 1
0 1 0
1 1 1
0 1 0

5