PROD1GCD - Product it again

The problem is very simple. given two integers n and m, find the product GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M).

Input

The first line will be the number of test cases t, followed by t lines, each having two numbers n and m (1 ≤ n, m ≤ 10000000) (1 ≤ t ≤ 5).

Output

Output the required solution modulo 109+7.

Example

Input:
1
5 6

Output:
5760

Added by:Abhinandan Agarwal
Date:2016-08-15
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2016-10-09 15:30:53
Question isn't that tough..NO Euler's Totient needed....just find patterns..try to squeeze as many calculations as possible and u r done wid it.... :)
2016-09-02 22:41:39
any other approach except memoization?
2016-09-02 21:07:00 Sarthak Munshi
memoization should help :)
2016-08-17 19:57:19
Is there a common formula for this sequence :-
gcd(1,n)*gcd(2,n)...*gcd(m,n) for two positive integers n,m ?
RE: not particularly, my solution is not O(1). Well, if you want, you can still try :-)

Last edit: 2016-08-17 20:40:40
2016-08-16 06:06:39 Rishav Goyal
@author : n > 5000000. look into test files. input files are wrong. please correct them asap.
RE: sorry for the inconvenience, I have updated the constraints, its 10^7 now !

Last edit: 2016-08-16 15:21:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.