题目背景

Spring has come true？

冬音在某次轮回时候本来给一季出的是这道题，但是由于作者怕大家看不懂 OI 题就换成将棋题了，因此被删除，已经过了 12 年了，于是在此放出原来的题。

题目描述

定义二元组乘法为：$(x,y)\times(a,b)=(x\times b+y\times a,x\times a+y\times b)$。

由于该乘法定义满足结合律（可自行验证），可以定义二元组的乘方：对二元组 $a$ 和正整数 $b$，$a^b$ 为 $b$ 个 $a$ 顺次相乘（由结合律可知不同计算顺序下结果唯一）。

定义两二元组 $(x,y)$ 和 $(a,b)$ 在模 $p$ 意义下相同当且仅当 $a\times y\equiv x\times b \pmod p$。（注意此处的相同未必具有传递性。）

冬音给出了一个长度为 $n$ 的二元组序列 $a$。

她希望一季能求出最多选出多少个长度为 $n$ 的正整数序列 $b$ 使得对于每个 $b$，$\prod_{i=1}^n a_i^{b_i}$ 在模 $p$ 意义下互不相同。保证 $\boldsymbol{p}$ 为质数。

求对于每一个区间的上面这个问题的答案的和对 $10^9+7$ 取模的结果。

输入格式

第一行，两个整数 $n,p$。保证 $\boldsymbol{p}$ 为质数。

接下来 $n$ 行，第 $i$ 行两个整数 $x_i,y_i$，表示 $a_i=(x_i,y_i)$。

输出格式

仅一行，一个整数，表示答案的和对 $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

提示

【样例解释 #1】

区间 $[1,1]$ 的答案为 $4$，其中一种选择方案中选择的 $b$ 分别为 $\{1\},\{2\},\{3\},\{4\}$。

区间 $[1,2]$ 的答案为 $1$，其中一种选择方案中选择的 $b$ 为 $\{1,1\}$。

区间 $[2,2]$ 的答案为 $1$，其中一种选择方案中选择的 $b$ 为 $\{1\}$。

【数据范围】

本题采用捆绑测试。

• 子任务 1（4 分）：$n\le2$，$p\le 5$。
• 子任务 2（8 分）：$n\le5$，$p\le 5$。
• 子任务 3（5 分）：$x_i=p-y_i$。
• 子任务 4（3 分）：$x_i=y_i$。
• 子任务 5（21 分）：$x_i=y_i-1$。
• 子任务 6（7 分）：$p=2$。
• 子任务 7（6 分）：$p=5$。
• 子任务 8（7 分）：$p\le 5003$。
• 子任务 9（8 分）：$p\le 10^9+7$。
• 子任务 10（14 分）：$p\le 10^{12}+39$。
• 子任务 11（17 分）：无特殊性质。

对于全部的数据，$1\le n\le 10^5$，$2\le p\le 10^{14}+67$，$0\le x_i,y_i<p$。保证 $\boldsymbol{p}$ 为质数。