Hex statistics

A sequence $S$ holds $N$ integers written in hexadecimal. Write $\mathrm{sum}(S)$ for the sum of all elements of $S$.

Let $p$ be a permutation of the 16 hexadecimal digits. Deleting a digit $d$ means erasing every occurrence of $d$ from every element of $S$. The digits that remain keep their order and are read as a hexadecimal number again, and an element that loses all of its digits becomes 0. A deletion can leave a 0 in front, which does not change the value.

Delete the digits one at a time in the order given by $p$ and record the sequence after each deletion. That gives 16 sequences. Writing $S[d_1,\dots,d_k]$ for the result of deleting the digits $d_1$ through $d_k$ from $S$, the 16 sequences are $S[p_1]$, $S[p_1,p_2]$, $\dots$, $S[p_1,\dots,p_{16}]$, and every element of the last one is 0. Define

$\mathrm{total}(S,p) = \mathrm{sum}(S[p_1]) + \mathrm{sum}(S[p_1,p_2]) + \dots + \mathrm{sum}(S[p_1,\dots,p_{16}])$

For example, take $S = [\texttt{9af47c0b}, \texttt{2545557}, \texttt{ff6447979}]$ and a permutation $p$ that starts with $\texttt{4}$, $\texttt{9}$, $\texttt{5}$. Deleting the digit $\texttt{4}$ gives $S[\texttt{4}] = [\texttt{9af7c0b}, \texttt{255557}, \texttt{ff67979}]$, and deleting the digit $\texttt{9}$ after that gives $S[\texttt{4},\texttt{9}] = [\texttt{af7c0b}, \texttt{255557}, \texttt{ff677}]$.

The value of $\mathrm{total}(S,p)$ depends on which permutation $p$ is used. Over all $16!$ permutations of the hexadecimal digits, compute three values: the smallest total, the largest total, and the sum of the totals of every permutation. Print the third value modulo 3b9aca07, which is $10^9+7$ in decimal. The first two are printed exactly, with no modulo taken.

The first line contains the length $N$ of the sequence. Each of the next $N$ lines contains one element $P$ of the sequence $S$, in input order. Every number in the input, including $N$, is written in hexadecimal with lowercase letters.

Constraints

• $\texttt{1} \le N \le \texttt{3f}$
• $\texttt{0} \le P \le \texttt{fffffffff}$

Print one line with three integers separated by single spaces, all in hexadecimal with lowercase letters: the smallest total, the largest total, and the sum of the totals of all $16!$ permutations modulo 3b9aca07.