Test Data Analysis

Time limit2sMemory limit256 MB

Summary

Count bounded arrays of length N whose maximum contiguous subarray sum equals D, modulo 1,000,000,007.

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

Problem

For an array $X$ of length $N$ , the maximum subarray problem asks for the largest sum of any contiguous subarray.

Each position $i$ must satisfy $A_i \leq X_i \leq B_i$ . Count how many different arrays $X$ have maximum subarray sum exactly $D$ . Print the count modulo $1{,}000{,}000{,}007$ .

Input

The first line contains an integer $T$ , the number of test cases.

Each test case begins with integers $N$ and $D$ ( $1 \leq N \leq 1000$ , $-1000 \leq D \leq 1000$ ).

The next $N$ lines give $A_i$ and $B_i$ ( $-1000 \leq A_i \leq B_i \leq 1000$ ) for each position.

Output

For each test case, print one line with the number of valid arrays modulo $1{,}000{,}000{,}007$ .

Note

When $D = 3$ and every range is $[-1, 2]$ with $N = 3$ , exactly 12 arrays reach maximum subarray sum 3.

Examples4

Example 1

Input

Expected output

12
1897

Example 2
Input
```
1
1 0
0 0
```
Expected output
```
1
```
Example 3
Input
```
1
1 5
1 5
```
Expected output
```
1
```
Example 4
Input
```
1
2 -1
-1 -1
-1 -1
```
Expected output
```
1
```