409879: GYM103821 K Movie Planning

You are planning to visit the movies with your friends after the end of the exams. The movie theater has $$$N$$$ movies, you know the start and end moments of each movie. The theater contains many halls, so there could be more than one movie playing at the same time, the movie theater will be open for $$$M$$$ moments.

If you reach the movies at the beginning of moment $$$L$$$ and you stay until the end of moment $$$R$$$, then you can watch any movie that starts at moment $$$L$$$ or later and ends at moment $$$R$$$ or earlier. You are planning to watch exactly $$$2$$$ complete movies, so you can't start watching the second movie until you finish watching the first one.

Since you are sharp-minded, you thought of all possible scenarios of arriving and leaving the movies, in other words, for every possible arriving time $$$L_i$$$ from $$$1$$$ to $$$M$$$, and for every possible leaving time $$$R_j$$$ from $$$L_i + 1$$$ to $$$M$$$. For each scenario you need to count how many pairs of movies are possible to watch during this period. You have to print the sum of pairs for all possible scenarios. Note that if some pair of movies is present in more than one scenario then you should count them independently in each scenario.

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 2\times{10^5}$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$N$$$ ($$$1\le{N}\le{2}\times{10}^5$$$) and $$$M$$$ ($$$1\le{M}\le{2}\times{10}^5$$$).

Each of the next $$$N$$$ lines of each test case contains $$$L_i$$$ and $$$R_i$$$($$$1\le{L_i}\le{R_i}\le{M}$$$), the start and the end moments of the $$$i^{th}$$$ movie for each $$$i$$$ from $$$1$$$ to $$$N$$$.

It is $$$\bf{guaranteed}$$$ that the sum of $$$N$$$ and sum of $$$M$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

For each test case, output a single integer denoting the answer for the test case, since the answer could be very large, please print the remainder of dividing it by $$$1\,000\,000\,007$$$.

2
3 6
1 3
2 5
3 6
4 12
1 6
2 8
9 10
11 12

0
21

In the first test case, all the movies are overlapping, in other words you can't pick two movies to watch entirely in any possible period of time, so the answer is $$$0$$$.