34613번 - Boarding Queue 다국어

문제

You are on your way to compete in The 2025 ICPC Asia Pacific Championship. Unfortunately, you are in the process of the worst part of flying: waiting in the boarding queue.

You are in a queue with $n$ travelers, numbered from 1ドル$ to $n$ ordered from the front of the queue to the back of the queue.

The boarding area is represented by a grid of $r$ rows and $c$ columns, where the rows are numbered from 1ドル$ to $r$ (top to bottom) and the columns are numbered from 1ドル$ to $c$ (left to right). Each traveler occupies exactly one distinct cell in the grid. Two travelers are adjacent if the cells they are in share an edge. Traveler $t$ and traveler $t − 1$ are guaranteed to be adjacent, for any 2ドル ≤ t ≤ n$.

For example, Figure L.1 illustrates a possible location of the travelers. In this example, traveler 1ドル$ is adjacent to travelers 2ドル$ and 10ドル$ but not adjacent to traveler 11ドル$.

Figure L.1: Example location of the travelers.

At each boarding step, all of the following happen simultaneously:

• The frontmost traveler in the queue, say traveler $t,ドル boards the aircraft and leaves the boarding area.
• For each $t'$ ($t + 1 ≤ t' ≤ n$), traveler $t'$ takes the cell that traveler $t' − 1$ was occupying immediately before the step.

For example, Figure L.2 illustrates the locations of the travelers after the first three boarding steps from the initial location above.

Figure L.2: Location of the travelers after 1ドル,ドル 2ドル,ドル and 3ドル$ boarding steps respectively.

You are traveler $p$ (that is, there are $p − 1$ travelers in front of you). You know that your team coach is somewhere in the queue, but you do not know where. Assuming your team coach is equally likely to be any of travelers 1ドル$ to $n$ (except $p$), you want to calculate the probability that you will be adjacent to your team coach at some point before you board the aircraft. Formally, you will be adjacent to traveler $q$ at some point before you board the aircraft if there exists an integer $s$ (0ドル ≤ s < p$) such that traveler $p$ and traveler $q$ are adjacent after s boarding steps.

입력

The first line of input contains four integers $r,ドル $c,ドル $n,ドル and $p$ (1ドル ≤ r, c ≤ 1000$; 2ドル ≤ n ≤ r \times c$; 1ドル ≤ p ≤ n$). Each of the next $r$ lines contains $c$ integers. The $j$-th integer in the $i$-th line denotes $G_{i,j}$ (0ドル ≤ G_{i,j} ≤ n$), where a non-zero value of $G_{i,j}$ means that traveler $G_{i,j}$ initially occupies the cell at row $i$ and column $j$ of the boarding area, while a zero value of $G_{i,j}$ means that no traveler occupies the cell. Across all pairs $(i, j),ドル each of the integers 1ドル$ to $n$ appears exactly once in $G_{i,j}$. The input guarantees that traveler $t$ and traveler $t − 1$ are adjacent, for all 2ドル ≤ t ≤ n$.

출력

Output a fraction in the $x/y$ format indicating the probability that you will be adjacent to your team coach at some point before you board the aircraft. The value of $y$ must be equal to $n − 1$. Note that there must not be spaces between the integers and the / delimiter.

제한

노트