D. 方格跳跃 (lattice)

小橙在玩一款通关游戏《方格跳跃》。每一关里，小橙操控着一个角色，从一条长廊的一端到达另一端。

长廊被划分成 个方格，从左到右依次编号为 ，小橙操控的角色一开始在编号为 的方格。

某些方格里有蹦床，只有在有蹦床的方格才能往右跳。从第 个蹦床开始最多可以跳过 个方格，即如果该蹦床所在方格为 ，则你最多能跳到编号为 的方格。

小橙想知道从编号为 的方格开始，最终到达编号为 的方格上，这样跳跃的方式有多少种。小橙很快就算出了答案，但他想考考你，你的结果应对 取模。

从文件 lattice.in 中读入数据。

第一行三个正整数 ，表示蹦床的个数、方格的个数和从编号为 的方格里的蹦床跳跃最多可以跳过的方格数。

接下来 行，每行两个正整数，第 行的两个正整数分别表示第 个蹦床所在方格的编号和从第 个蹦床跳跃最多可以跳过的方格数。

输出到文件 lattice.out 中。

仅一行一个整数表示答案。

样例 1 输入

3 5 3
2 1
4 1

样例 1 输入

1

样例 2 输入

5 7 2
2 2
6 1
4 1
5 2

样例 2 输入

2

对于 的数据，；

对于另外 的数据，对于任意的 ；

对于 的数据，。