Rabbit Dance in Directed Graph

There is a directed graph with \((L+1) \times n\) vertices. Each vertex is represented as a tuple \((u,v)\) where \(0 \le u \le L\) and \(1 \le v \le n\). The graph is a multigraph: for any two vertices \((u_1,v_1)\) and \((u_2,v_2)\), if \(u_1 < u_2\) there are exactly \(w[v_1][v_2]\) distinct edges from \((u_1,v_1)\) to \((u_2,v_2)\); if \(u_1 \ge u_2\) there is no edge.

The white rabbit starts at the vertex \((0,x)\). It may perform a sequence of jumps (possibly zero) following these rules. In each step, from the current vertex \((u,v)\), the rabbit may choose any vertex \((u',v')\) with \(u' > u\) and traverse one of the \(w[v][v']\) edges between them. The rabbit may stop at any time. However, if it reaches a vertex with \(u = L\) it must stop since no outgoing edges exist.

When the rabbit stops after making \(m\) moves (\(m\) can be zero), it records its dance as a sequence of edges taken. Two dances are considered different if they have different lengths or there is at least one step where the chosen edge differs.

Given positive integers \(k\) and \(y\) (with \(1 \le y \le n\)), for each remainder \(t\) (\(0 \le t < k\)) count the number of dances (of any length \(m\)) ending at a vertex whose second coordinate is \(y\) and such that \(m \bmod k = t\). Output the answers modulo \(p\).

Note on the graph: From any vertex \((u,v)\) (with \(u < L\)), a jump is performed by choosing any \(u'\) such that \(u' \in \{u+1, u+2, \dots, L\}\) and any vertex \(v'\) (\(1 \le v' \le n\)). The number of distinct edges in that jump is \(w[v][v']\). Even if two jumps go to the same second coordinate, if they land in different layers (i.e. different \(u'\)) they are considered distinct.

inputFormat

The input is given as follows:

L n k p
x y
w[1][1] w[1][2] ... w[1][n]
w[2][1] w[2][2] ... w[2][n]
...
w[n][1] w[n][2] ... w[n][n]

Here, \(L, n, k, p, x, y\) are positive integers. The matrix \(w\) is an \(n \times n\) matrix where \(w[i][j]\) indicates the number of edges from a vertex with second coordinate \(i\) to a vertex with second coordinate \(j\) (when the first coordinate increases).

outputFormat

Output \(k\) integers separated by spaces. The \(t\)th number (for \(t = 0, 1, \dots, k-1\)) is the number of dances whose number of moves \(m\) satisfies \(m \bmod k = t\) and that end at a vertex with second coordinate \(y\), modulo \(p\).

sample

1 2 2 1000
1 1
1 2
3 4

1 1