CERI2018K - Sum of divisors

no tags 

The goal of the problem is to compute the sum of divisor for some integers $N$.

Assume that number $N = p_0^{e_0} \times p_1^{e_1} \times \cdots p_k^{e_k}$, where $p_i$ are prime numbers, and $e_i$ are positive integers.

Input

The first line of the input consist of a single integer number $t$ which determines the number of tests.

Each test is on two separate lines.

In each test,

  • on the first line, there is two integer numbers $k$, and $m$.
  • on the second line, there is $2(k+1)$ integer numbers $p_i$ and $e_i$, with $p_i$ a prime number.

Constraints

  • $0 < t \leqslant 256$ ;
  • $0 \leqslant k \leqslant 1000$ ;
  • $0 < m \leqslant 2\times10^9$ ;
  • $1 < p_i < 2\times10^9$, a prime number ;
  • $0 < e_i < 2\times10^9$.

Output

For each test case, you are given a prime factorization of $N$, you'll have to print the sum of divisors of $N$, modulo $m$.

Example

Input:
3
0 1000
17,1
2 100
2,1 5,1 7,2
1 1000
3,1 1000000007,1
Output:
18
26
32

Explanation

For the first test case, $N = 17^1$, whose sum of divisors is $18$.

For the second test case, $N = 2^1 \times 5^1 \times 7^2 = 490$, whose sum of divisors is $?$.


hide comments
wisfaq: 2018-05-08 15:01:42

The same: whom=>whose
=(Francky)=> Thanks

Last edit: 2018-05-08 19:48:09
[Rampage] Blue.Mary: 2018-05-08 08:45:11

My program doesn't use division at all.

nadstratosfer: 2018-05-08 05:24:41

This being a tutorial problem, I suppose it's fair to ask for a hint: how to deal with p-1's that are not invertible mod m?

=(Francky)=> A way is to compute your numerator modulo m*(p-1), and then divide by (p-1) to get your answer modulo m. You'll need better than usual modular multiplication (using C), or the use of Python for easy coding.

[NG]: Thanks!

Last edit: 2018-05-08 20:50:58

Added by:Francky
Date:2018-05-08
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All