Description

年轻人 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$ 取模的结果。

Input Format

输入文件的第一行包含两个整数 $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})$。

Output Format

输出文件的唯一一行必须包含一个整数——分配梦秒数的方式数量，对 $10^{9} + 7$ 取模。

3 1
4 3
2 2
2 1

15

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。