406343: GYM102367 E XOR Pairing

There are $$$N$$$ stones with non-negative integers $$$x_0, \ldots, x_{N-1}$$$ written on them, where $$$N$$$ is even. We are to partition the stones into $$$N \over 2$$$ pairs, with each stone belonging to exactly one pair. For each pair, we calculate $$$x_i$$$ XOR $$$x_j$$$ by writing each of $$$x_i$$$ and $$$x_j$$$ in binary, taking the exclusive-or of each pair of corresponding bits, and interpreting the resulting bits as a binary number. We sum the values $$$x_i$$$ XOR $$$x_j$$$ over all the pairs of stones. The task is to find the minimum possible value of this overall sum over all possible pairings of the given stones. Furthermore, you are to find the number of stone pairings that achieve this minimal overall sum. Two pairings are considered to be different if one has a pair of stones that the other one does not have. Two stones are considered to be different if they have different indices, even if the value written on them is the same. The order of the pairs and the order of stones inside each pair is not significant. Since the number of such pairings can be huge, output it modulo $$$10^9+7$$$.

The first line contains one even number $$$N$$$, the number of stones, satisfying $$$2 \leq N \leq 74$$$. The second line contains the $$$N$$$ numbers written on the stones, $$$x_0, \ldots, x_{N-1}$$$. Each number satisfies $$$0 \leq x_i \leq 1000$$$.

Output one line containing two numbers separated by a space: the smallest possible overall sum of the pairs $$$x_i$$$ XOR $$$x_j$$$ over all pairings, and the number of pairings that achieve this minimum sum modulo $$$10^9+7$$$.

6
7 14 17 4 2 1

31 3