SPOJ.com - Problem FACTMULP

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.

Submit solution!

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

Submit solution!

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