CERI2018K  Sum of divisors
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:
20180508 15:01:42
The same: whom=>whose


[Rampage] Blue.Mary:
20180508 08:45:11
My program doesn't use division at all. 

nadstratosfer:
20180508 05:24:41
This being a tutorial problem, I suppose it's fair to ask for a hint: how to deal with p1's that are not invertible mod m?

Added by:  Francky 
Date:  20180508 
Time limit:  1s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 