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 ≤ 109
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:
2014-05-17 23:08:41
There's something very strange with input ; I shouldn't get 0.33 on sub_11598340. ???
|
|
Min_25:
2014-05-17 18:20:27
@Francky
|
|
abhijith reddy d:
2009-11-29 05:17:20
So many pointless optimizations are needed :-/ |
|
~!(*(@*!@^&:
2009-04-19 02:35:34
what is the hell of the optimization? |
|
[Trichromatic] XilinX:
2009-04-14 11:06:47
Heavy optimizations needed. |
|
~!(*(@*!@^&:
2009-04-14 07:45:03
time is strict for this problem? 1s? |
Added by: | Ajay Somani |
Date: | 2007-09-07 |
Time limit: | 1s |
Source limit: | 2048B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | "The Art of Computer Programming" |