DETER2 - Find The Determinant II

no tags 

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
10192
Note: 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. ???
I'll email admins, but I can't guaranties an answer. It was a buggy submission for me ; the same code get 0.41s few minutes latter.
--edit--> Now I have a much faster starting algo, it's the crux.(0.13s of init(); , then 0.04s for the 20 cases.).

Last edit: 2014-05-18 17:14:49
Min_25: 2014-05-17 18:20:27

@Francky
My time complexity (per case) is better (less) than O(N).
--ans(Francky)--> Thanks, I think I found a way to do so.
--ans(Francky)2--> My previous comment were deleted by accident/bug (your comment disappeared for a while ???, and I deleted mine...) I said I had a (per case) complexity of 2N modular multiplications, and Nlog(N) subtractions, and got TLE. Now I have a faster way. I think once you have the good method (not easy), the only optimization is obvious regarding constraints. Nice problem. I wonder if rank#1 submission is a buggy one, or not ??? (it rarely happened, but did)
--ans(Francky)3-->Now I think I know why your comment disappeared for a while : it was on another tab on my browser ; not refreshed !

Last edit: 2014-05-22 20:52:34
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"