That Time I Got Reincarnated as a Slime Researcher (Hard)

Hi there! My name is ntopia.

I used to be an ordinary man in my twenties living on Earth. One day a stranger stabbed me on the street and I died. When I came to, I had landed in another world, and here I seem to have become a slime researcher who studies nothing but slimes. Right now I am running a very important piece of research. If it succeeds, I get to return to the world I came from. Will you help me with it?

Every slime here carries something called slime energy, and the amount is a natural number of at least 2. I study how slime energy changes when slimes are merged.

A merge takes 2 slimes and produces 1. Merge a slime with slime energy $A$ and a slime with slime energy $B$, and you get one slime whose slime energy is $A \times B$.

The merging technique is not perfect yet, so every merge burns a lot of electric energy. To be precise, merging a slime with slime energy $A$ and a slime with slime energy $B$ needs $A \times B$ units of electric energy.

A slime with energy 4 merged with a slime with energy 6. The merge spends $4 \times 6$ units of electric energy and produces a slime with slime energy 24.

I have $N$ slimes right now, and I want to merge all of them down to a single slime. My laboratory told me it will bill me the product of the electric energy spent at every merge step. So my goal is to pick the merge order that makes that product as small as possible.

Help me with my research! Please!

The first line has the number of test cases $T$, followed by $T$ test cases.

The first line of each test case has the number of slimes $N$ ($1 \le N \le 60$). The second line has $N$ natural numbers, where the $i$-th number $C_i$ ($2 \le C_i \le 2 \times 10^{18}$) is the slime energy of the $i$-th slime.

The energy of the single slime left after every merge of a test case is guaranteed to be at most $2 \times 10^{18}$.

The sum of $N$ over all test cases is at most 1,000,000.

For each test case, print on its own line the minimum billed cost of merging every slime into one, taken modulo 1,000,000,007. When no electric energy is needed at all, that is when $N = 1$, print 1.