SP1772 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.

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} $

One line corresponding to each test case containing the determinant modulo 1000003 for the corresponding test case.