Background

Spring has come true？

This problem was originally prepared by Fuyune for Kazuho during a certain cycle of time but was replaced with a shogi problem due to the author's concern about the difficulty of OI problems. After 12 years, the original problem is now released here.

Problem 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