In this problem, we want to apply a linear transformation to warp an N dimensional vol- ume. Let V olume(v) denote the volume of the N dimensional parallelepiped spanned by N, N dimensional vectors {v1, v2, . . . , vN }. An exam- ple of a 2D volume spanned by 2, 2 dimensional vectors is shown below. In a strange twist, we have decided to apply a “Linear GCD” trans- formation. That is, if we represent our linear transformation f : RN → RN by the matrix A, where R denotes the set of real numbers, then A(i,j) = gcd(i,j) for 1 ≤ i,j ≤ N, where gcd(i,j) stands for the greatest common divi- sorofiandj. Given,S,anysetofNvec- tors of RN, such that Volume(S) is positive, we ask you to compute the ratio of the vol- ume after the transformation to the volume be- fore the GCD Transformation. In other words, compute r(S) = Volume(F(S))/Volume(S), where F(S) = {f(v)|v in S}. However, since r(S) can be quite large, we only ask you to com- pute T(S) = floor(r(S)) mod 4000039. In an even stranger twist, we will not give you S, but instead ask you to compute, the mean value of T(S) over all N vectors S of RN , such that V olume(S) is positive. Input The input of each test cases is simply the value N (N < 4000000) on its own line. Output For each input value, output the answer rounded to an integer, followed by a newline. Sample Input 10000 10001 Sample Output 2747606 295638