FACTMULP - Product of factorials (hard)

no tags 

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.


hide comments
Curiosa: 2017-09-29 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.
@edit, fixed it goddamn i feel dumb.
yet another really nice problem Francky.

Last edit: 2017-09-29 15:31:27
Abhishek pratap singh: 2016-02-21 13:45:48

@francky: Can you tell me if i'm missing a tricky case or the formula i'm using is wrong?

=(Francky)=> Sorry for late answer ; it seems you found a way to get AC ;-)

Last edit: 2016-02-24 13:14:20
ashishn42: 2015-12-31 01:52:16

@Francky - I just need to know if their is some problem with logic or am I missing some tricky cases ? Thanks.

=(Francky)=> You have some few good answers. Good luck.

Last edit: 2015-12-31 12:21:42
Maroof: 2015-06-21 12:00:00

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

=(Francky)=> I saw few WA, there's tricky cases ; you have to figure what they are. Good luck.

Last edit: 2015-06-22 01:36:42
Adarsh kumar: 2015-05-21 21:07:09

Cool problem .. would have been more interesting without those warning :-)

abdou_93: 2014-12-06 13:30:20

finaly AC i am really happy :D
thanks @francky

--ans--> You're welcome.

Last edit: 2014-12-06 13:49:29
aqfaridi: 2014-03-14 14:33:51

@francky
i m getting WA in python .. my formula is wrong or is there any tricy testcase ?? id : 11247492
--ans(Francky)--> Based on 11246877, (your last Python submissions didn't output anything) your formula seems good, but it's clearly stated in description that there are tricky cases ; you have to figure what can be those ones, it's part of the problem. You will be happy to find them : for me the problem exists only for those cases. Good luck ;-)

Last edit: 2014-03-14 14:49:59
aqfaridi: 2014-03-14 12:20:09

why O(log(e)) per testcase solution giving TLE ?? id:11246877
--ans(Francky)--> pike seems a bit slow for that task. I'll take a look if I can increase time limit for allow pike AC. Waiting for that : you can make a one-liner in Python ;-), if you want.

Last edit: 2014-03-14 12:29:41
abdou_93: 2014-03-03 23:01:29

why WA ?
can you give me any case ?
--ans(francky)--> Most of your output consist of WA. You should build some cases with brute force to debug your code. Warning : after that, don't forget that there are tricky cases too.

can you tell me if there is lots of WA , for the last submission ?
--ans(francky)--> 50%. The tricky cases. Good luck for them. ;-)

WA WA WA :( :(

The last thing .. please tell me if my formula wrong or not .
i wrote it in last code .
--ans(francky)--> It's not the simplest, but a correct one. Now you have few WA. I won't help more. Good luck.

Last edit: 2014-03-04 13:52:27

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