16진수 통계

16진수로 표기된 정수 $N$개가 수열 $S$를 이룬다. $\mathrm{sum}(S)$는 $S$의 모든 원소를 더한 값이다.

16진수 숫자 16개를 한 번씩 나열한 순열을 $p$라고 하자. 숫자 $d$를 지운다는 것은 $S$의 모든 원소에서 $d$를 전부 지운다는 뜻이다. 남은 숫자는 순서를 그대로 지킨 채 다시 16진수로 읽고, 숫자가 하나도 남지 않은 원소는 0이 된다. 지운 뒤 맨 앞에 0이 와도 값은 달라지지 않는다.

$p$의 순서대로 숫자를 하나씩 지우면서 매 단계의 수열을 기록하면 수열 16개를 얻는다. $S[d_1,\dots,d_k]$를 $S$에서 숫자 $d_1$부터 $d_k$까지 지운 결과라고 쓰면, 이 16개는 $S[p_1]$, $S[p_1,p_2]$, $\dots$, $S[p_1,\dots,p_{16}]$이고 마지막 수열은 모든 원소가 0이다. 여기서 다음과 같이 정의한다.

$\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}])$

예를 들어 $S = [\texttt{9af47c0b}, \texttt{2545557}, \texttt{ff6447979}]$이고 $p$가 $\texttt{4}$, $\texttt{9}$, $\texttt{5}$로 시작하면, 숫자 $\texttt{4}$를 지운 $S[\texttt{4}]$는 $[\texttt{9af7c0b}, \texttt{255557}, \texttt{ff67979}]$이고 이어서 숫자 $\texttt{9}$를 지운 $S[\texttt{4},\texttt{9}]$는 $[\texttt{af7c0b}, \texttt{255557}, \texttt{ff677}]$이다.

$\mathrm{total}(S,p)$는 어떤 순열 $p$를 쓰는지에 따라 달라진다. 16진수 숫자의 순열 $16!$개를 모두 고려해서 세 값을 구하라. 가장 작은 total, 가장 큰 total, 그리고 순열마다 얻은 total을 모두 더한 값이다. 세 번째 값은 3b9aca07으로 나눈 나머지를 출력한다. 이 수는 10진수로 $10^9+7$이다. 앞의 두 값은 나머지를 취하지 않고 그대로 출력한다.

첫째 줄에 수열의 길이 $N$이 주어진다. 다음 $N$개의 줄에는 수열 $S$의 원소 $P$가 입력 순서대로 한 줄에 하나씩 주어진다. $N$을 포함해 입력의 모든 수는 소문자를 쓰는 16진수다.

제한

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

한 줄에 세 정수를 공백 하나로 구분해 소문자 16진수로 출력한다. 차례대로 가장 작은 total, 가장 큰 total, 그리고 $16!$개 순열의 total을 모두 더한 값을 3b9aca07으로 나눈 나머지다.