P12011 【MX-X10-T7】[LSOT-4] 春开，意遥遥。

> 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$ 取模的结果。

无

无

**【样例解释 #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