Description

It is said that a tempting treasure is hidden on the top floor of a distant Treasure Tower. After many hardships, Xiao Ming finally finds the legendary Treasure Tower. At the entrance stands a wooden board with big characters: Treasure Hunt Manual. The manual reads as follows:

The Treasure Tower has $N+1$ floors. The topmost floor is the top floor, and there is a room on the top floor that contains the treasure. Except for the top floor, there are $N$ other floors, each with $M$ rooms. These $M$ rooms form a circle and are numbered in counterclockwise order as $0,\cdots,M-1$. Some rooms have stairs leading to the floor above, and the stair layout may be different on each floor. In each room there is a signboard with a number $x$. Starting from this room, choose the $x$-th room with stairs in counterclockwise order (suppose its index is $k$), go upstairs from that room, and after going up you will arrive at room $k$ on the floor above. For example, if the signboard in the current room says $2$, then start searching counterclockwise and find the second room that has stairs, and go upstairs from that room. If the current room itself has stairs to the upper floor, it is counted as the first room with stairs.

At the end of the manual, in large red characters, it says: "Treasure Hunt Notice: The sum of the numbers on the signboards that help you find the room to go upstairs on each floor (that is, the number on the signboard in the first room entered on each floor) is the key to open the treasure chest."

Please help Xiao Ming compute this key to open the treasure chest.

Input Format

The first line contains two integers $N$ and $M$, separated by a space. $N$ means there are $N$ floors other than the top floor, and $M$ means there are $M$ rooms on each floor other than the top floor.

The next $N \times M$ lines each contain two integers separated by a space, describing the situation in one room. The $(i-1) \times M + j$-th line describes room $j-1$ on floor $i$ ($i=1,2,\cdots,N$; $j=1,2,\cdots,M$). The first integer indicates whether this room has stairs to the floor above ($0$ means no, $1$ means yes). The second integer is the number on the signboard. Note that if you climb the stairs from room $j$ to the floor above, you will arrive at room $j$ on that floor.

The last line contains one integer, which is the index of the room on the bottom floor where Xiao Ming starts the treasure hunt (note: room indices start from $0$).

Output Format

Output one integer: the key to open the treasure chest. This number can be very large, so output it modulo $20123$.

2 3
1 2
0 3
1 4
0 1
1 5
1 2
1

5

Hint

Constraints

For $50\%$ of the testdata, $0 < N \le 1000$, $0 < x \le 10^4$.
For $100\%$ of the testdata, $0 < N \le 10000$, $0 < M \le 100$, $0 < x \le 10^6$.

NOIP 2012 Junior, Problem 2.

Translated by ChatGPT 5