A square board of size $m \times m$ is given. The rows and columns of the board are numbered from $1$ to $m$.
You need to place chips on the board so that each cell contains at most one chip. In addition, $n$ constraints must be satisfied. In the $i$-th constraint, two integers $r_i$ and $c_i$ are given, meaning that in the rectangle consisting of cells with coordinates $[1 \ldots r_i] \times [1 \ldots c_i]$, there may be at most one chip.
Determine the remainder modulo $10^9 + 7$ of the number of different chip placements that satisfy all constraints.
Input Format
The first line of the input contains integers $n$ and $m$ — the number of constraints and the size of the board ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^9$).
The next $n$ lines each contain two integers $r_i$ and $c_i$ ($1 \le r_i, c_i \le m$).
Output Format
Output one number — the number of valid chip placements modulo $10^9 + 7$.
Scoring
| Subtask | Points | Additional constraints | Required subtasks |
|---|---|---|---|
| 1 | 3 | $n \le 10$, $m \le 4$ | — |
| 2 | 6 | $n = 1$, $m \le 1000$ | — |
| 3 | 8 | $n \le 10$, $m \le 1000$ | 1, 2 |
| 4 | 8 | $n \le 15$, $m \le 10^9$ | 1–3 |
| 5 | 10 | $n \le 2500$, $m \le 100$ | 1 |
| 6 | 10 | $n \le 2500$, $m \le 250$ | 1, 5 |
| 7 | 10 | $n \le 2500$, $m \le 1000$ | 1–3, 5, 6 |
| 8 | 10 | $n \le 2500$, $m \le 10^5$ | 1–3, 5–7 |
| 9 | 15 | $n \le 2 \cdot 10^5$, $m \le 2 \cdot 10^5$ | 1–3, 5–8 |
| 10 | 20 | no additional constraints | 1–9 |
Example
standard input
1 4 4 4
standard output
17
standard input
2 2 1 2 2 1
standard output
10
standard input
3 5 2 5 3 4 4 4
standard output
4480
Note
In the first example, at most one chip can be placed on the entire board. There are $4 \times 4 = 16$ ways to place one chip and $1$ way with zero chips placed.