题目描述

传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的藏宝楼，藏宝楼的门口竖着一块木板，上面写着寻宝说明书。

说明书内容如下：

藏宝楼共有 $N+1$ 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除顶层外藏宝楼另有 $N$ 层，每层有 $M$ 个房间，这 $M$ 个房间围成一圈并按逆时针方向依次编号为 $0,1,\dots,M-1$。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字 $x$，表示从这个房间开始按逆时针方向选择第 $x$ 个有楼梯的房间（假定该房间的编号为 $k$），从该房间上楼。如果当前房间本身就有楼梯通向上一层，那么当前房间会被视为第一个有楼梯的房间。

寻宝须知：打开宝箱的密钥为每进入一层时所在的房间的指示牌数字的总和（初始进入最底层计入总和），最终结果需要对 $20123$ 取模。

请帮助小明算出打开宝箱的密钥，小明将从藏宝楼最底层（第 1 层）的指定编号房间开始寻宝。

输入格式

第一行 2 个整数 $N$ 和 $M$，之间用一个空格隔开。$N$ 表示除顶层外藏宝楼共有 $N$ 层，$M$ 表示除顶层外每层楼有 $M$ 个房间。

接下来 $N \times M$ 行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况：

第 $(i-1) \times M + j$ 行（$i=1,2, \dots, N$; $j=1,2, \dots, M$）表示第 $i$ 层、实际编号为 $j-1$ 的房间的情况：

第一个整数表示该房间是否有楼梯通往上一层（$1$ 表示有，$0$ 表示没有），第二个整数表示指示牌上的数字 $x$。

最后一行，一个整数，表示小明从藏宝楼底层（第 1 层）进入的房间编号（编号从 $0$ 开始）。

输出格式

输出只有一行，一个整数，表示打开宝箱的密钥对 $20123$ 取模的结果。

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

5

数据规模与约定

对于 50% 的数据：$0 < N \le 1000$，$0 < x \le 10000$ 对于 100% 的数据：$0 < N \le 10000$，$0 < M \le 100$，$0 < x \le 1000000$