P12011 【MX-X10-T7】[LSOT-4] Spring, the Distant Wish

> 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.

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$.

- 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)$.

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

**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