SPOJ.com - Problem DETER2

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 ≤ 10⁹

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.

Submit solution!

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?

Submit solution!

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"