DETER - Find The Determinant
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), 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 500000), each of the following T lines contain an integer N the size of the matrix. N lies between 1 and 2000000 ( both inclusive ).
Output
One line corresponding to each test case containing the determinant modulo 1000003 for the corresponding test case.
Example
Input: 3 1 3 5 Output: 1 2 16
hide comments
BugsBunny :):
2011-11-29 19:58:01
:( |
|
[Trichromatic] XilinX:
2009-04-10 03:28:19
This problem is moved to tutorial section because a similar (almost the same) problem MSE08H is available in the classical section. |
|
Ajay Somani:
2009-03-31 15:59:01
second. |
|
~!(*(@*!@^&:
2009-03-18 17:03:27
In which book? 1st, 2nd ...? |
Added by: | Ajay Somani |
Date: | 2007-09-01 |
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" |