Was the 2022 APC really that hard?

Interview

Time limit1sMemory limit1024 MB

Summary

Count the sequences of N difficulties where each D_i lies in [a_i, b_i] and adjacent values differ by at most K, modulo 1e9+7.

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

Problem

In 2022, the APC was harder than the problem setters expected. To control difficulty, Hyeonbin, a setter for the 2023 APC, wrote a difficulty guideline. The 2023 APC will have $N$ problems, numbered 1 through $N$ in order.

Hyeonbin's guideline has two rules.

The difficulty $D_{i}$ of problem $i$ is an integer that satisfies $a_{i} \leq D_{i} \leq b_{i}$ .
The difficulty gap between adjacent problems is at most $K$ . In other words, $|D_{i}-D_{i+1}| \leq K$ holds for every $i$ .

For Hyeonbin, count the number of ways to set the difficulties of the $N$ problems while following the guideline's rules.

Input

The first line contains $N$ and $K$ . $(1\leq N\leq 3\,000; 0\leq K \leq 3\,000)$

From the second line onward, the next $N$ lines each contain $a_{i}$ and $b_{i}$ , separated by a space. $(1\leq a_{i} \leq b_{i} \leq 3\,000)$

All values in the input are integers.

Output

Print the number of ways to set the difficulties of the $N$ problems that satisfy the conditions, modulo $10^{9}+7$ .

Hint

Sorry about that.

Examples2

Example 1
Input
```
4 3
1 7
2 3
4 6
3 7
```
Expected output
```
140
```
Example 2
Input
```
3 0
1 7
2 6
3 5
```
Expected output
```
3
```