spoj#FACTMULP. Product of factorials (hard)
Product of factorials (hard)
For n positive integer, let F(n) = 1! × 2! × 3! × 4! × ... × n!, product of factorial(i) for i in [1..n],
For p a prime number, and n an integer,
and let V(p, n) = max({i>=0 integer, such that p^i divides F(n)}).
Input
The first line of input contains an integer
T, the number of test cases.
On each of the next T lines, your are given
two integers p a prime number, and e.
Output
For each test case, you have to print V(p, p^e).
As the answer may not fit in a 64-bit container, just output your answer modulo 10^9+7.
Example
Input: 1 2 2
Output: 5
Constraints
0 < T < 10^5 1 < p < 10^18, a prime number 0 < e < 10^18
p and e are log-uniform independent randomly distributed. Warning : input contains tricky cases too.
A single line of human-readable-Python code can get AC in the third of the time limit. A fast C code ends in 0.04s. (edit 2017-02-11, after compiler changes)
;-) Have fun.