当前没有测试数据。

本题由于测试点个数限制，暂无法评测。

题目描述

你有一个 $n$ 个小段依次放置组成的长条，每一个小段中有 $a_i$ 个方格，最开始每一个方格都是白色的。

你需要将若干个位置染成黑色，要求染色之后满足以下限制：

• 每一个小段中至少有 $b_i$ 个方格是白色的。
• 任意两个黑色的格子中间至少有 $k$ 个格子都是白色。

求染色方案数对 $10^9+7$ 取模的方案数。

输入格式

第一行两个正整数 $n,k$。

接下来 $n$ 行每行两个正整数 $a_i,b_i$。

输出格式

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

样例 $1$

样例 $1$ 输入

3 1
4 3
2 2
2 1

样例 $1$ 输出

15

数据范围

本题采用捆绑测试。

对于 $20\%$ 的数据，$1\leq n\leq 5,1\leq a_i\leq 5,0\leq k\leq 10$；

对于全部数据，$1\leq n\leq 1000,1\leq a_i\leq 250,0\leq b_i\leq a_i,0\leq k\leq 100$。