Problem Description

You are given a square board of size $m \times m$. 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. At the same time, you must satisfy $n$ constraints. The $i$-th constraint gives two integers $r_i$ and $c_i$, meaning that in the rectangular area with coordinates $[1 \ldots r_i] \times [1 \ldots c_i]$, at most one chip can be placed.

Compute the number of different chip placement schemes that satisfy all constraints, and output the result modulo $10^9+7$.

Input Format

The first line of the input contains two integers $n$ and $m$ — the number of constraints and the size of the board ($1 \le n \leq 2 \cdot 10^5$, $1 \leq m \le 10^9$).

The next $n$ lines each contain two numbers $r_i$ and $c_i$ ($1 \le r_i, c_i \le m$).

Output Format

Output one number — the number of valid chip placement schemes modulo $10^9+7$.

1 4
4 4

17

2 2
1 2
2 1

10

3 5
2 5
3 4
4 4

4480

Hint

Sample Explanation

In the first sample, 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 to place no chips.

Scoring Rules

Translated by DeepSeek.

Translated by ChatGPT 5