Kebab House

Time limit2sMemory limit256 MB

Summary

Count subsets of the work seconds with gaps of at least t+1 such that each kebab misses at most q_i minus x_i ingredients, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

Vahtang Bumerang makes kebabs at the fast food chain Kebab House. One kebab holds many ingredients.

This morning Vahtang got an order for $n$ kebabs. He puts $q_1$ ingredients into the first kebab, then $q_2$ ingredients into the second one, and so on in that order. Putting in one ingredient takes exactly one second, so the $i$ -th kebab takes $q_i$ seconds, and he starts the next kebab the moment he finishes one. The whole job therefore runs without a break for $q_1 + q_2 + \dots + q_n$ seconds, numbered 1, 2, 3 and so on from the moment he starts.

While he works, Vahtang keeps thinking of his beloved boomerang and drifts into a daydream. Each dream lasts exactly one second, and during that second he forgets to put in an ingredient. He never dreams twice inside any $t+1$ consecutive seconds, so the numbers of two dream seconds always differ by at least $t+1$ .

Because of the dreams a kebab can end up with fewer ingredients than intended. Customer $i$ is happy when the $i$ -th kebab holds at least $x_i$ ingredients.

Compute the number of ways to choose the dream seconds so that every customer is happy, modulo $10^9+7$ . Two ways count as different when the sets of dream seconds differ.

Input

The first line contains the number of kebabs $n$ and the value $t$ that sets the minimum spacing between dream seconds ( $1 \le n \le 1000$ , $0 \le t \le 100$ ).

The $i$ -th of the next $n$ lines contains $q_i$ , the number of ingredients meant for the $i$ -th kebab, and $x_i$ , the smallest number of ingredients that makes the $i$ -th customer happy ( $1 \le q_i \le 250$ , $0 \le x_i \le q_i$ ).

Output

Print on one line the number of ways to choose the dream seconds so that every customer is happy, modulo $10^9+7$ .

Examples4

Example 1
Input
```
3 1
4 3
2 2
2 1
```
Expected output
```
15
```
Example 2
Input
```
1 0
1 0
```
Expected output
```
2
```
Example 3
Input
```
1 100
1 1
```
Expected output
```
1
```
Example 4
Input
```
2 0
3 1
2 0
```
Expected output
```
28
```