Distinct Tuple‐Power Products

We are given a sequence of pairs (a_1,a_2,\dots,a_n) where each (a_i=(x_i,y_i)) is a pair of integers. Define the multiplication of two pairs as follows: [ (x,y)\times(a,b)=(x\times b+y\times a,; x\times a+y\times b). ] It can be verified that the above multiplication is associative (though not having an identity element in general) so that for any positive integer (b) the power (a^b) is defined as the product of (b) copies of (a) (the result does not depend on the order of multiplication).

We introduce an equivalence relation under a prime modulus (p) on pairs: we say two pairs ((x,y)) and ((a,b)) are equivalent modulo (p) if and only if [ a\times y\equiv x\times b\pmod{p}. ] (Notice that this relation does not necessarily satisfy transitivity.)

Define for any positive integer sequence (b=(b_1, b_2, \dots, b_m)) (each (b_i) is a positive integer) the product [ P(b)=\prod_{i=1}^m a_i^{b_i}, ] where the multiplication and exponentiation are defined as above. For a fixed sequence (a_1,a_2,\dots, a_m) (with (m\ge 1)) one may choose many (m)-tuples (b) of positive integers. However, by the periodicity of exponentiation (explained below) the number of distinct equivalence classes of the product (P(b)) is finite. In fact, one may show that after a suitable change of variable the problem reduces to the following.

For each pair (a=(x,y)) define [ U=x+y, \quad V=x-y. ] If (V\equiv 0\pmod{p}) (i.e. (x\equiv y\pmod{p})) then we say the corresponding order (d=1) (since in that case (a^b=(U^b,0)) is always equivalent to each other). Otherwise, define the associated number [ r = \frac{U}{V} = \frac{x+y}{x-y} \pmod{p}. ] Since (p) is prime, (r) is an element of the multiplicative group (\mathbb{F}_p^) (which is cyclic) and hence the set ({r^b;:; b\ge1}) is finite. Let (d) be the order of (r) in (\mathbb{F}_p^); that is, (d) is the smallest positive integer such that [ r^d\equiv 1\pmod{p}. ] Then as (b) runs over all positive integers, the set of distinct pairs (a^b) (up to the equivalence defined above) has exactly (d) elements.

Now, given a sequence (a_1,a_2,\dots,a_n) we are interested in the following question. For any contiguous sub‐sequence (a_l,a_{l+1},\dots,a_r) ((1\le l\le r\le n)) consider choosing a positive integer sequence (b=(b_l,b_{l+1},\dots,b_r)) so that the products [ P(b)=\prod_{i=l}^{r} a_i^{b_i} ] (from the sub‐sequence) are pairwise non–equivalent (that is, if (b) and (b') are two distinct sequences then the corresponding products are not equivalent modulo (p)). It turns out that the maximum number of choices one can have (over all possible selections of (b)) equals the number of distinct products obtainable. A short computation shows that if for each (i) we define (d_i) as above (i.e. (d_i=1) when (x_i-y_i\equiv0\pmod{p}), and otherwise (d_i) is the order of (\frac{x_i+y_i}{x_i-y_i}) in (\mathbb{F}p^*)), then the number of distinct products over the sub–sequence (a_l,\dots,a_r) is exactly [ \mathrm{lcm}(d_l,d{l+1},\dots,d_r). ]

Your task is: given (n) and a prime (p), and the (n) pairs (a_1,a_2,\dots,a_n), compute the sum of answers for all contiguous sub–sequences, i.e., [ S=\sum_{1\le l\le r\le n} ;\mathrm{lcm}(d_l,d_{l+1},\dots,d_r), ] and output (S) modulo (10^9+7).

Input and output format details are given below.

inputFormat

The first line contains two integers (n) and (p) (with (p) prime).

Then follow (n) lines. The (i)th of these lines contains two integers (x_i) and (y_i) representing the pair (a_i=(x_i,y_i)).

outputFormat

Output a single integer, the sum of the answers for every contiguous sub–sequence modulo (10^9+7).

sample

3 7
1 2
2 3
3 1

18