In this problem, we will consider a simple two-dimensional heat transfer model. We start by assuming that we have some rectangular room of dimension \(n \times m\) which we divide into a grid. Let's call the cell on the \(i^{th}\) row and the \(j^{th}\) column as \((i, j)\). Inside the grid, we will randomly scatter a handful of heaters. The initial temperature of the cell\((i, j)\) is denoted by \(T_{ij}^{0}\) which is \(1\) units if there is a heater, \(0\) units otherwise. At every step in time, there is some heat flow between a cell and its neighbours. The update equation of temperature of cells \((i, j)\) at time step \(z \rightarrow z + 1\) looks as

\(T_{ij}^{z + 1} = T_{ij}^{z} + \sum_{x,y \in neigbours}{k \times (T_{xy}^{z} - T_{ij}^{z})}\)

In the equation for updating the cell’s temperature, the constant \(k\) simply represents the rate at which heat flows. The neighbors of cell \((i, j)\) are the cells which shares a side with cell \((i, j)\) i.e we consider only four neighbors (top, bottom, left, right).

Given the initial temperature of cells in the grid, Can you tell the temperature of cells after \(x\) time steps. Since the temperature of cells can be very large output the temperature modulo \(10^9 + 7\).

Constraints:

\(2 \le n, m\le 10\)
\(1 \le k \le 10\)
\(1 \le x \le 10^9\)
\(0 \le T_{ij}^{0} \le 1\)

Input Format:

The first line contains four space-separated integers \(n, m, k, \text{ and } x.\)

Next \(n\) lines contain \(m\) integers \(j^{th}\) interger in \(i^{th}\) line is \(T_{ij}^{0}\). The initial temperature of cell \((i, j)\).

Output Format:

Output \(n\) lines, each containing \(m\) integer. \(j^{th}\) interger in \(i^{th}\) line denotes the temperature of cell \((i, j)\) after \(x\) time steps.