该题作为 2025 年 4 月官方月赛 T2

题目描述

遥远的地方矗立着一座神秘的宝藏塔。史蒂夫历经千辛万苦终于找到了这座传说中的宝藏塔，塔的入口处放着一块刻有神秘符文的黑曜石，上面记录着寻宝指南。

宝藏塔的结构与规则：

• 宝藏塔一共有 $N + 1$ 层，最上面一层是塔顶，塔顶的一个房间里藏着珍贵的宝藏。除了塔顶外，宝藏塔还有 $N$ 层，每层有 $M$ 个房间 ，这些房间围成一圈，并且按逆时针方向依次编号为 $0, \cdots, M - 1$。

• 部分房间设有通往上层的传送门（由末地传送门框架和末影之眼组成）。每层通往上层的传送门情况可能不同。

• 每个房间里都有一个用红石灯显示数字的告示牌，告示牌上的数字 $x$ 表示从这个房间开始，按逆时针方向选择第 $x$ 个有传送门的房间（假定房间的编号是连续的 ），从该房间通过传送门可以到达上一层的对应房间。例如，如果当前房间告示牌上写着 $2$，那么就按逆时针方向找到第 $2$ 个有传送门的房间，从这个房间上楼，上楼后到达上一层的对应房间。如果当前房间本身就有传送门通向上层，那么这个房间就作为第 $1$ 个有传送门的房间。

寻宝关键：

• 寻宝指南的最后用醒目的金块文字写着：“关键线索：帮助找到每层上楼房间告示牌上的数字（即每层第一个进入的房间内告示牌上的数字）总和，这个总和就是打开宝箱的密码。”

现在请帮助史蒂夫算出打开宝箱的密码。由于这个数字可能很大，请输出对 20123 取模的结果即可。

输入格式

第一行是用空格隔开的两个整数 $N$ 和 $M$。分别表示表示除顶层外宝藏塔共 $N$ 层，以及除顶层外每层有 $M$ 个房间。

接下来 $N \times M$ 行，每行有两个用空格隔开的整数，描述一个房间内的情况。其中 $(i - 1) \times M + j$ 行表示第 $i$ 层 $j - 1$ 号房间的情况（$i \in \{ 1, 2, \cdots , N \}；j \in \{1, 2, \cdots , M\}$）。 每行输入中第一个整数表示该房间是否有传送门通向上一层（0 表示没有，1 表示有），第二个整数表示告示牌上的数字。注意，从 $j$ 号房间通过传送门到上一层到达的房间一定也是 $j$ 号房间。

最后一行，一个整数，表示史蒂夫从宝藏塔底层的几号房间进入开始寻宝（房间编号从 $0$ 开始 ）。

输出格式

一个整数，表示打开宝箱的密码，由于这个数字可能很大，请输出对 20123 取模的结果即可。

输入输出样例

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

5

说明 / 提示

数据范围与约定

对于 $100\%$ 的数据，$1 \le N,M \le 5000$。