ChefGame

All submissions for this problem are available.
Everyone knows that ChefLand is the best country in the world and all of its people are the happiest. However, nobody knows their secret of being happy.
Suraj is an Indian scientist and his goal is to research the life of ChefLandian people. He has already arrived in ChefTown, the capital of ChefLand, and met Chef. He promised to reveal their secret to Suraj if he gets maximal score in a special ChefLandian game. The game has following rules:
 In Ddimensional Euclidean space, N lattice points are given. Every pair of points are not connected initially. The points are not guaranteed to be distinct.
 Let (A_{1}, A_{2}, ..., A_{D}) and (B_{1}, B_{2}, ..., B_{D}) be the coordinates of the points A and B respectively, then the distance between A and B is defined as ( (A_{1}−B_{1})^{2} + (A_{2}−B_{2})^{2} + ... + (A_{D}−B_{D})^{2} )^{1/2}.
 The initial Suraj's score is 1.
 Suraj is allowed to take as many turns as he wants.
 In every turn, Suraj can connect an unconnected pair of two given points, if this new connection does not form a cycle. That is, Suraj cannot connect the pair of points A and B, if there exist points X_{1}, X_{2}, ..., X_{k} such that A connected to X_{1}, X_{1} connected to X_{2}, X_{2} connected to X_{3},..., and X_{k} connected to B.
 In every time Suraj connects some points, his score is multiplied by the square of the distance between them.
Now Suraj wonders what is the maximal score he can get. Write a program that will find this score. Since this number can be huge you should output it modulo 747474747.
Input
The first line of input contains T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains two spaceseparatedintegers N and D. The next N lines contain D spaceseparated integers, denoting the coordinates of the given lattice points.
Output
For each test case, output the maximal score modulo 747474747.
Constrains
 1 ≤ T ≤ 6666
 1 ≤ N ≤ 6666
 1 ≤ D ≤ 5
 The absolute value of any integer given in the input does not exceed 100000000 (10^{8}).
 The sum of N in one input file does not exceed 6666.
Example
Input: 1 3 2 0 0 1 1 1 1 Output: 8
Explanation
The distance between the first point and the second point is ((0−(−1))^{2}+(0−(−1))^{2})^{1/2} = 2^{1/2}.
The distance between the first point and the third point is ((0−1)^{2}+(0−(−1))^{2})^{1/2} = 2^{1/2}.
The distance between the second point and the third point is (((−1)−1)^{2}+((−1)−(−1))^{2})^{1/2} = 2.
One of the optimal ways is that Suraj connects the third and the second points, and then connects the first and the second points. The maximum score is 2^{2} * (2^{1/2})^{2} = 8.
Author:  rubanenko 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/CHEFGAME 
Tags  Rubanenko, april13, medium, mst, prim 
Date Added:  10122012 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 