年轻的 Vahtang Bumerang 在世界著名的快餐连锁店 Kebab House 制作烤肉串。每个烤肉串包含许多配料。

今天早上，Vahtang 接到了制作 $n$ 个烤肉串的订单。首先，他需要往第一个烤肉串中放入 $q_1$ 个配料，然后往第二个烤肉串中放入 $q_2$ 个配料，以此类推。Vahtang 放入一个配料需要花费一秒钟，因此制作第 $i$ 个烤肉串需要 $q_i$ 秒。当他完成一个烤肉串后，会立即开始制作下一个。

Vahtang 在制作烤肉串时经常会梦到他心爱的回旋镖。每次做梦恰好持续一秒钟，在这期间 Vahtang 会忘记往烤肉串中放入一个配料。幸运的是，在任何连续的 $(t + 1)$ 秒内，他最多只会做一次梦。

由于做梦，一些烤肉串的配料数量可能会少于预期的数量，但只要第 $i$ 个烤肉串中至少有 $x_i$ 个配料，顾客仍然会感到满意。

Vahtang 想要计算在保持所有顾客满意的前提下，他在工作期间出现做梦时刻的方案数。你能帮帮他吗？由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入的第一行包含两个整数 $n$ 和 $t$ —— 烤肉串的数量以及两次做梦时刻之间至少需要间隔的时间（$1 \le n \le 1000$；$0 \le t \le 100$）。

接下来的 $n$ 行，每行包含两个整数 $q_i$ 和 $x_i$ —— 第 $i$ 个烤肉串所需的配料总数以及使第 $i$ 个顾客满意的最少配料数（$1 \le q_i \le 250$；$0 \le x_i \le q_i$）。

输出格式

输出一行一个整数 —— 分配做梦时刻的方案数，对 $10^9 + 7$ 取模。

样例

输入 1

3 1
4 3
2 2
2 1

输出 1

15