Kalel 是一只喜欢跳石头的青蛙。 有 $N$ 块石头排成一排，从左到右编号为 $1$ 到 $N$。Kalel 从第 $1$ 块石头开始，想要到达第 $N$ 块石头。 在每一步中，Kalel 可以从 $M$ 种跳跃方式中选择一种。第 $j$ 种跳跃方式允许他从石头 $x$ 跳到石头 $x + d_j$，并消耗 $p_j$ 点能量。对于某些 $j$，$p_j$ 可能等于 $0$。你可以假设 Kalel 的能量永远不会耗尽。 给定 $N$ 和 $K$，计算 Kalel 到达第 $N$ 块石头时总共消耗不超过 $K$ 点能量的方法数。如果跳跃选择的序列不同，则视为两种不同的方式。由于这个数字可能非常大，我们只关心它对 $10^9$（十亿）取模后的余数。

输入格式

第一行包含三个整数 $N$、$M$ 和 $K$ ($1 \le N \le 10^9$, $1 \le M \le 10^5$, $0 \le K \le 400$)。 接下来的 $M$ 行，每行包含两个整数 $d_j$ 和 $p_j$ ($1 \le d_j \le 10$, $0 \le p_j \le K$)。

输出格式

输出一行，表示 Kalel 到达第 $N$ 块石头且总能量消耗不超过 $K$ 点的不同方法数，对 $10^9$（十亿）取模。

样例

样例输入 1

5 3 10
1 3
2 0
3 1

样例输出 1

6

样例输入 2

100000 3 10
1 9
2 0
7 3

样例输出 2

85449877