Description

Define the multiplication of ordered pairs as:

$$(x,y) \times (a,b) = (x \times b + y \times a,\ x \times a + y \times b).$$

Since this multiplication satisfies the associative law (verification is left to the reader), we can define the exponentiation of ordered pairs: for an ordered pair $a$ and a positive integer $b$, $a^b$ represents the product of $b$ copies of $a$ (the result is unique due to associativity).

Two ordered pairs $(x,y)$ and $(a,b)$ are considered identical under modulo $p$ if and only if

$$a \times y \equiv x \times b \pmod{p}.$$

Note: This "identity" is not necessarily transitive.

Fuyune provides a sequence of $n$ ordered pairs $a$.

She asks Kazuho to determine the maximum number of length-$n$ positive integer sequences $b$ that can be selected such that for each $b$, the products $\prod_{i=1}^n a_i^{b_i}$ are pairwise distinct under modulo $p$. It is guaranteed that $p$ is a prime.

Compute the sum of the answers for all intervals $[l, r]$ (where $1 \le l \le r \le n$), modulo $10^9+7$.

Input Format

• The first line contains two integers $n$ and $p$. It is guaranteed that $p$ is a prime.
• The next $n$ lines each contain two integers $x_i$ and $y_i$, representing the ordered pair $a_i = (x_i, y_i)$.

Output Format

A single integer, the sum of answers for all intervals modulo $10^9+7$.

2 5
3 4
2 3

6

7 3
2 2
1 2
1 0
2 1
1 1
2 1
2 0

30

8 935259307
761834349 406479726
404588595 588271872
835094749 847811683
52046622 489905911
530455310 402465343
616226641 808848730
891363714 745033395
207684362 101456684

46008831

Hint

Sample Explanation #1

• For interval $[1,1]$, the answer is $4$. One valid selection includes sequences $\{1\}, \{2\}, \{3\}, \{4\}$.
• For interval $[1,2]$, the answer is $1$. One valid selection is $\{1,1\}$.
• For interval $[2,2]$, the answer is $1$. One valid selection is $\{1\}$.

Data Range

This problem uses subtasks with bundled testing.

• Subtask 1 (4 pts): $n \le 2$, $p \le 5$.
• Subtask 2 (8 pts): $n \le 5$, $p \le 5$.
• Subtask 3 (5 pts): $x_i = p - y_i$.
• Subtask 4 (3 pts): $x_i = y_i$.
• Subtask 5 (21 pts): $x_i = y_i - 1$.
• Subtask 6 (7 pts): $p = 2$.
• Subtask 7 (6 pts): $p = 5$.
• Subtask 8 (7 pts): $p \le 5003$.
• Subtask 9 (8 pts): $p \le 10^9+7$.
• Subtask 10 (14 pts): $p \le 10^{12}+39$.
• Subtask 11 (17 pts): No additional constraints.

For all test cases:
$1 \le n \le 10^5$,
$2 \le p \le 10^{14}+67$,
$0 \le x_i, y_i < p$.
It is guaranteed that $p$ is a prime.

Translation by DeepSeek R1