FACTMULP  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 64bit 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 loguniform independent randomly distributed. Warning : input contains tricky cases too.
A single line of humanreadablePython code can get AC in the third of the time limit. A fast C code ends in 0.04s. (edit 20170211, after compiler changes)
;) Have fun.
hide comments
Curiosa:
20170929 11:36:47
Hi @francky, could you please check my last submission? I think I covered the tricky cases too. but still wa : I'd appreciate some help.


Abhishek pratap singh:
20160221 13:45:48
@francky: Can you tell me if i'm missing a tricky case or the formula i'm using is wrong?


ashishn42:
20151231 01:52:16
@Francky  I just need to know if their is some problem with logic or am I missing some tricky cases ? Thanks.


Maroof:
20150621 12:00:00
@francky can you tell me if there are lots of WAs in my last submission and is my formula correct?


Adarsh kumar:
20150521 21:07:09
Cool problem .. would have been more interesting without those warning :) 

abdou_93:
20141206 13:30:20
finaly AC i am really happy :D


aqfaridi:
20140314 14:33:51
@francky


aqfaridi:
20140314 12:20:09
why O(log(e)) per testcase solution giving TLE ?? id:11246877


abdou_93:
20140303 23:01:29
why WA ?

Added by:  Francky 
Date:  20140301 
Time limit:  4.300s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 