题目描述

The young man Vahtang Bumerang makes kebabs at the world-famous fast-food chain Kebab House. Each kebab contains many ingredients.

This morning Vahtang has received an order to make $n$ kebabs. At first, he should put $q_{1}$ ingredients to the first kebab, then $q_{2}$ ingredients in the second one and so on. Vahtang spends one second to put one ingredient to a kebab, so it takes $q_{i}$ seconds to make the i-th kebab. When he finishes the kebab he immediately proceeds to the next one.

Vahtang often dreams about his lovely boomerang while making kebabs. Each dream takes exactly one second and Vahtang forgets to put one ingredient to kebab during this second. Fortunately, he never dreams twice in any consecutive $(t + 1)$ seconds.

Due to dreams about boomerang, some kebabs may have lesser than the desired number of ingredients, but customers are still happy if the $i$-th kebab has at least $x_{i}$ ingredients in it.

Vahtang wants to calculate the number of ways to have dream seconds during his work while keeping all customers happy. Can you help him? The real answer may be very huge, so you have to calculate it modulo $10^{9} + 7$ .

输入格式

The first line of the input file contains two integers $n$ and $t$ — the number of kebabs and minimal possible time between dream seconds $(1 \le n \le 1000$ ; $0 \le t \le 100)$ .

Each of the next $n$ lines contains two integers $q_{i}, x_{i}$ — the number of ingredients in the $i$-th kebab and the minimum number of ingredients to make the $i$-th customer happy $(1 \le q_{i} \le 250$ ; $0 \le x_{i} \le q_{i}).$

输出格式

The only line of the output file must contain one integer -- the number of ways to distribute dream seconds modulo $10^{9} + 7$ .

题目大意

题目描述

一个叫Vahtang Bumerang的年轻人在世界知名的连锁快餐店做肉串，每个肉串包含许多成分。

今晨，VB接到了一个肉串订单，首先，他应该将$q_{1}$种配料放入第一个烤肉串，将$q_{2}$种配料放入第二个，依此类推。VB将一种配料放进一个肉串需要 $1$ 秒，所以做第 $i$ 个肉串需要 $q_{i}$ 秒。当他完成一个肉串时，他会立即制作一个肉串。

VB在做肉串时经常梦见他可爱的boomerang，做一次梦要一秒钟，而VB却忘了在这一秒钟里将一种配料放到肉串上。幸运的是，他从不在任何连续的 $(t + 1)$ 秒内做梦超过一次。

由于梦见boomerang，一些肉串可能少于订单所需的配料数量，但如果第 $i$ 个肉串中至少含有 $x_{i}$ 种配料，则客户仍然会感到满意。

VB想知道在让顾客开心的前提下自己有多少种不同的梦见boomerang的方案，请你计算在满足条件下分配做梦秒数的方法数量，答案可能很大，请输出其对$10^{9} + 7$ 取模的结果。

输入格式

第一行包含两个整数 $n$ 和 $t$ ，表示烤肉串的数量和两次幻想之间的最小可能秒数。$(1 \le n \le 1000, 0≤t≤100)$

接下来 $n$ 行，每行包含两个整数 $q_{i}, x_{i}$ 表示第 $i$ 个订单规定肉串中的配料数量以及使第 $i$ 个客户满意的最少配料数量。$(1 \le q_{i}≤250 ; 0 \le x_{i} \le q_{i})$

输出仅一行，包含一个整数-以模数形式分配梦想秒数的方法数量在 $mod$ $10^9+7$ 意义下的答案。

说明/提示

时间限制: 2 s, 空间限制: 256 MB

3 1
4 3
2 2
2 1

15

提示

Time limit: 2 s, Memory limit: 256 MB.