전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

안녕? 내 이름은 ntopia야.

나는 원래 지구에서 평범하게 살던 20대 청년이었어. 어느 날 길을 걷다가 괴한의 칼에 찔려 죽고 말았지. 그런데 정신을 차려 보니 이세계에 떨어져 있는 거야. 여기에서 나는 슬라임을 전문으로 연구하는 슬라임 연구자가 된 것 같아. 지금 아주 중요한 연구를 진행하고 있는데, 이 연구가 성공하면 원래 살던 세계로 돌아갈 수 있어. 이 연구를 도와주지 않을래?

이곳의 슬라임은 모두 슬라임 에너지라는 것을 갖고 있고, 그 양은 2 이상의 자연수로 나타내. 나는 슬라임을 합성했을 때 슬라임 에너지가 어떻게 변하는지를 연구하고 있어.

합성은 슬라임 2마리를 재료로 1마리를 만들어 내는 과정이야. 슬라임 에너지가 $A$인 슬라임과 $B$인 슬라임을 합성하면 슬라임 에너지가 $A \times B$인 슬라임 1마리가 나와.

합성 기술이 아직 완벽하지 않아서 한 번 합성할 때마다 전기 에너지가 크게 들어. 구체적으로, 슬라임 에너지가 $A$인 슬라임과 $B$인 슬라임을 합성하려면 전기 에너지가 $A \times B$만큼 필요해.

슬라임 에너지가 4인 슬라임과 6인 슬라임을 합성한 모습. 전기 에너지 $4 \times 6$을 써서 슬라임 에너지가 24인 슬라임이 만들어졌다.

나에겐 지금 슬라임이 $N$마리 있어. 이 슬라임을 전부 합성해서 마지막에 1마리로 만들려고 해. 그런데 내가 있는 연구소에서 각 합성 단계에 들어간 전기 에너지를 전부 곱한 값을 비용으로 청구하겠다고 했어. 그래서 이 값이 최소가 되도록 합성 순서를 정하는 것이 내 연구의 목표야.

내 연구를 도와줘! 부탁이야!

첫 줄에 테스트 케이스의 수 $T$가 주어지고, 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 슬라임의 수 $N$ ($1 \le N \le 60$)이 주어진다. 둘째 줄에는 자연수 $N$개가 주어지며, 그중 $i$번째 수 $C_i$ ($2 \le C_i \le 2 \times 10^{18}$)는 $i$번째 슬라임의 슬라임 에너지다.

한 테스트 케이스의 슬라임을 끝까지 합성하고 난 뒤에 남는 슬라임 한 마리의 에너지는 $2 \times 10^{18}$ 이하임이 보장된다.

모든 테스트 케이스의 $N$을 더한 값은 1,000,000을 넘지 않는다.

각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구되는 비용의 최솟값을 1,000,000,007로 나눈 나머지를 한 줄에 하나씩 출력한다. 전기 에너지가 전혀 필요하지 않은 경우, 즉 $N = 1$인 경우에는 1을 출력한다.