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.