DETER2  Find The Determinant II
In this problem you have to calculate the determinant of an N x N matrix whose entries are given by m[i][j] = gcd(i,j)^{k}, 1 ≤ i,j ≤ N.
Here gcd(i,j) denotes the greatest common divisor of i and j.
As the determinant D can grow very large, you have to print D%1000003.
Input
First line of input consists of a single integer containing the number of test cases T ( equal to around 20), each of the following T lines contain two integers N and k where N is the size of the matrix and k is the exponent.
1 ≤ N ≤ 1000000
1 ≤ k ≤ 10^{9}
Output
One line corresponding to each test case containing the determinant modulo 1000003 for the corresponding test case.
Example
Input: 3 4 2 2 4 4 3 Output: 288 15 10192Note: You may want to solve DETER first, in case you havent already solved it.
hide comments
Francky:
20140517 23:08:41
There's something very strange with input ; I shouldn't get 0.33 on sub_11598340. ???


Min_25:
20140517 18:20:27
@Francky


abhijith reddy d:
20091129 05:17:20
So many pointless optimizations are needed :/ 

~!(*(@*!@^&:
20090419 02:35:34
what is the hell of the optimization? 

[Trichromatic] XilinX:
20090414 11:06:47
Heavy optimizations needed. 

~!(*(@*!@^&:
20090414 07:45:03
time is strict for this problem? 1s? 
Added by:  Ajay Somani 
Date:  20070907 
Time limit:  1s 
Source limit:  2048B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  "The Art of Computer Programming" 