I. Ahmad and Gifting Syndrome
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad needed to stop gifting people an array of integers, so he decided to gift Monther a bunch of intervals this time!

Ahmad gifted Monther $$$n$$$ intervals, and he is interested in the number of ways you can choose one integer from each of the $$$n$$$ intervals such that the sum of these integers is divisible by $$$k$$$.

More formally, he is interested in the number of ways to choose $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ where ($$$l_i \leq x_i \leq r_i$$$) and their sum $$$\sum_{i=1}^{n}x_i$$$ is divisible by $$$k$$$.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 2 \cdot 10^5; 1 \leq k \leq 10)$$$.

The next $$$n$$$ lines of the test case each contain two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq l_i \leq r \leq 10^9)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.

Output

For each test case, print the number of ways you can choose an array $$$x$$$ as described above modulo $$$10^9 + 7$$$.

Example
Input
3
2 3
1 3
1 3
3 3
1 4
1 5
1 6
4 4
1 12
1 14
1 15
1 20
Output
3
40
12600